Generate All Combinations Sum K in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does 'Generate All Combinations Sum K' mean?

It means finding all unique groups of numbers from a list that add up exactly to a target number K.

beginner

Why do we sort the input list before generating combinations?

Sorting helps to avoid duplicate combinations and makes it easier to stop early when the sum exceeds K.

intermediate

What is backtracking in the context of generating combinations?

Backtracking is a method where we build combinations step-by-step and remove the last number if it doesn't lead to a solution, then try another number.

intermediate

How do we avoid duplicate combinations in this problem?

By skipping numbers that are the same as the previous one at the same recursion level, we prevent repeating the same combination.

beginner

What is the base case for the recursive function in generating combinations sum K?

When the current sum equals K, we add the current combination to the result list and stop exploring that path.

What should you do if the current sum exceeds K during combination generation?

A Stop exploring this path and backtrack

B Continue adding numbers

C Restart from the beginning

D Ignore the sum and add anyway

If the sum is greater than K, no need to continue because adding more numbers will only increase the sum.

Why is it important to skip duplicate numbers at the same recursion level?

A To increase the sum

B To reduce time complexity

C To avoid duplicate combinations

D To sort the list

Skipping duplicates prevents generating the same combination multiple times.

What data structure is commonly used to store the current combination during recursion?

A Queue

B Stack or list

C Hash map

D Tree

A list or stack is used to keep track of the current numbers chosen.

What is the main purpose of sorting the input array before recursion?

A To help skip duplicates and prune search

B To change the target sum

C To print results in order

D To use binary search

Sorting helps to easily skip duplicates and stop early when sums exceed K.

When do you add the current combination to the result list?

A When sum is less than K

B At the start of recursion

C When sum is greater than K

D When sum equals K

Only combinations that sum exactly to K are valid and added.

Explain how backtracking helps in generating all combinations that sum to K.

Think about trying numbers one by one and undoing choices when needed.

Describe the role of sorting and skipping duplicates in this problem.

How does order help in pruning and uniqueness?

Practice

1. What does the problem "Generate All Combinations Sum K" ask you to find?

easy

A. All unique combinations of numbers that add up to K

B. The largest number less than K

C. The sum of all numbers from 1 to K

D. The product of all numbers that divide K

Solution

1. Step 1: Understand the problem goal

   The problem asks to find all unique sets of numbers that add exactly to the target sum K.

2. Step 2: Clarify what combinations mean

   Combinations mean groups of numbers without regard to order, and each number can be used once or multiple times depending on problem rules.

3. Final Answer:

   All unique combinations of numbers that add up to K -> Option A

4. Quick Check:

   Combinations sum K = unique sets summing to K [OK]

Hint: Focus on sums equal to K, not products or counts [OK]

Common Mistakes:

• Confusing sum with product
• Looking for single numbers instead of combinations
• Ignoring uniqueness of combinations

2. Which Rust syntax correctly defines a function header to generate combinations summing to k with candidates as a slice of integers?

easy

A. fn combination_sum(candidates: Vec<i32>, k: i32) -> Vec<i32>

B. fn combination_sum(candidates: Vec<i32>, k: i32) -> i32

C. fn combination_sum(candidates: &[i32], k: i32) -> i32

D. fn combination_sum(candidates: &[i32], k: i32) -> Vec

Solution

1. Step 1: Identify input types

   The candidates are passed as a slice reference &[i32] to avoid ownership issues and allow read-only access.

2. Step 2: Identify return type

   The function returns a vector of vectors of i32, representing all combinations found.

3. Final Answer:

   fn combination_sum(candidates: &[i32], k: i32) -> Vec -> Option D

4. Quick Check:

   Function signature with slice input and Vec output [OK]

Hint: Use &[i32] for input slice and Vec for combinations [OK]

Common Mistakes:

• Returning i32 instead of combinations
• Using Vec<i32> input causing ownership issues
• Wrong return type for multiple combinations

3. What is the output of this Rust code snippet?

fn main() {
    let candidates = vec![2, 3, 6, 7];
    let target = 7;
    let result = combination_sum(&candidates, target);
    println!("{:?}", result);
}

fn combination_sum(candidates: &[i32], target: i32) -> Vec {
    fn backtrack(start: usize, target: i32, path: &mut Vec<i32>, res: &mut Vec, candidates: &[i32]) {
        if target == 0 {
            res.push(path.clone());
            return;
        }
        for i in start..candidates.len() {
            if candidates[i] > target {
                continue;
            }
            path.push(candidates[i]);
            backtrack(i, target - candidates[i], path, res, candidates);
            path.pop();
        }
    }
    let mut res = vec![];
    let mut path = vec![];
    backtrack(0, target, &mut path, &mut res, candidates);
    res
}

medium

A. [[3, 3, 3], [7]]

B. [[2, 3, 6], [7]]

C. [[2, 2, 3], [7]]

D. [[2, 2, 2, 3]]

Solution

1. Step 1: Understand backtracking logic

   The function tries combinations starting from each candidate, allowing repeats, and collects those summing to target 7.

2. Step 2: Trace valid combinations

   Valid combinations are [2, 2, 3] (2+2+3=7) and [7] itself.

3. Final Answer:

   [[2, 2, 3], [7]] -> Option C

4. Quick Check:

   Backtracking finds combinations summing to 7 [OK]

Hint: Check sums carefully; 2+2+3 and 7 match target [OK]

Common Mistakes:

• Including invalid sums like 2+3+6
• Ignoring repeated use of candidates
• Missing single element combination [7]

4. Identify the bug in this Rust function for generating combinations summing to k:

fn combination_sum(candidates: &[i32], target: i32) -> Vec {
    fn backtrack(start: usize, target: i32, path: &mut Vec<i32>, res: &mut Vec, candidates: &[i32]) {
        if target == 0 {
            res.push(path.clone());
            return;
        }
        for i in start..candidates.len() {
            if candidates[i] >= target {
                continue;
            }
            path.push(candidates[i]);
            backtrack(i, target - candidates[i], path, res, candidates);
            path.pop();
        }
    }
    let mut res = vec![];
    let mut path = vec![];
    backtrack(0, target, &mut path, &mut res, candidates);
    res
}

medium

A. The recursive call should use i + 1 instead of i

B. The condition should be candidates[i] > target, not >= target

C. The path vector should not be cloned when pushing to res

D. The function should return i32 instead of Vec

Solution

1. Step 1: Analyze the pruning condition

   The condition 'if candidates[i] >= target' skips candidates equal to target, missing valid combinations like [target] itself.

2. Step 2: Correct the condition

   Changing to 'candidates[i] > target' allows candidates equal to target to be included, fixing the bug.

3. Final Answer:

   The condition should be candidates[i] > target, not >= target -> Option B

4. Quick Check:

   Pruning must allow candidates equal to target [OK]

Hint: Use >, not >=, to include candidates equal to target [OK]

Common Mistakes:

• Skipping candidates equal to target
• Incorrect recursive index causing duplicates
• Not cloning path before pushing

5. Given candidates = [1, 2, 3] and target = 4, which of the following is the correct set of all unique combinations summing to 4, assuming candidates can be used unlimited times?

hard

A. [[1,1,1,1], [1,1,2], [1,3], [2,2]]

B. [[1,1,1,1], [1,1,2], [2,2], [3,1]]

C. [[1,1,1,1], [1,1,2], [1,3], [2,2], [3,1]]

D. [[1,1,1,1], [1,1,2], [1,3], [2,2], [4]]

Solution

1. Step 1: List all combinations summing to 4

   Possible combinations using unlimited candidates are [1,1,1,1], [1,1,2], [1,3], and [2,2].

2. Step 2: Check for duplicates and invalid entries

   [3,1] is a duplicate of [1,3] (order doesn't matter), and [4] is invalid as 4 is not in candidates.

3. Final Answer:

   [[1,1,1,1], [1,1,2], [1,3], [2,2]] -> Option A

4. Quick Check:

   Unique combinations without duplicates or invalid numbers [OK]

Hint: Exclude duplicates and numbers not in candidates [OK]

Common Mistakes:

• Including duplicates with different order
• Adding numbers not in candidates
• Missing valid combinations