Generate All Combinations Sum K in DSA Rust

Mental Model

Find all groups of numbers from a list that add up exactly to a target number.

Analogy: Imagine you have a box of different coins and want to find all ways to pick some coins that add up to exactly one dollar.

Candidates: [2, 3, 6, 7]
Target: 7

Start with empty combination []
Try adding numbers one by one to reach sum 7

[]
↓
[2]
↓
[2, 2]
↓
[2, 3]
...

Each arrow means adding a number and checking sum

Dry Run Walkthrough

Input: candidates: [2, 3, 6, 7], target: 7

Goal: Find all combinations of numbers from candidates that sum to 7

Step 1: Start with empty combination [] and target 7

Combination: [] (sum 0), Target left: 7

Why: We begin with no numbers chosen and full target to reach

Step 2: Add 2 to combination: [2], reduce target to 5

Combination: [2] (sum 2), Target left: 5

Why: Try including 2 and see if we can reach target 7

Step 3: Add 2 again: [2, 2], reduce target to 3

Combination: [2, 2] (sum 4), Target left: 3

Why: We can reuse numbers, so try 2 again

Step 4: Add 3: [2, 2, 3], reduce target to 0

Combination: [2, 2, 3] (sum 7), Target left: 0

Why: Sum matches target, so this is a valid combination

Step 5: Backtrack: remove last 3, try next candidate 6 at [2, 2]

Combination: [2, 2], Target left: 3

Why: 3 did not lead to other solutions, try next number

Step 6: Add 6: [2, 2, 6], target left -3 (negative), discard

Combination: [2, 2, 6] invalid (sum 10 > 7)

Why: Sum exceeded target, so discard this path

Step 7: Backtrack to [2], try next candidate 3: [2, 3], target left 2

Combination: [2, 3], Target left: 2

Why: Try next number after 2 to find other combos

Step 8: Add 3 again: [2, 3, 3], target left -1 (negative), discard

Combination: [2, 3, 3] invalid (sum 8 > 7)

Why: Sum exceeded target, discard path

Step 9: Backtrack to [2], try next candidate 6: [2, 6], target left -1, discard

Combination: [2, 6] invalid (sum 8 > 7)

Why: Sum exceeded target, discard path

Step 10: Backtrack to [], try candidate 3: [3], target left 4

Combination: [3], Target left: 4

Why: Try starting with 3

Step 11: Add 3 again: [3, 3], target left 1

Combination: [3, 3], Target left: 1

Why: Reuse 3 to get closer to target

Step 12: Add 3 again: [3, 3, 3], target left -2, discard

Combination: [3, 3, 3] invalid (sum 9 > 7)

Why: Sum exceeded target, discard path

Step 13: Backtrack to [3, 3], try 6: [3, 3, 6], target left -5, discard

Combination: [3, 3, 6] invalid (sum 12 > 7)

Why: Sum exceeded target, discard path

Step 14: Backtrack to [3], try 6: [3, 6], target left -2, discard

Combination: [3, 6] invalid (sum 9 > 7)

Why: Sum exceeded target, discard path

Step 15: Backtrack to [], try 6: [6], target left 1

Combination: [6], Target left: 1

Why: Try starting with 6

Step 16: Add 6 again: [6, 6], target left -5, discard

Combination: [6, 6] invalid (sum 12 > 7)

Why: Sum exceeded target, discard path

Step 17: Backtrack to [], try 7: [7], target left 0

Combination: [7], Target left: 0

Why: Sum matches target, valid combination

Result:

Valid combinations:
[2, 2, 3]
[7]

Annotated Code

DSA Rust

fn combination_sum(candidates: &[i32], target: i32) -> Vec<Vec<i32>> {
    fn backtrack(
        candidates: &[i32],
        target: i32,
        start: usize,
        current: &mut Vec<i32>,
        results: &mut Vec<Vec<i32>>,
    ) {
        if target == 0 {
            results.push(current.clone()); // found valid combo
            return;
        }
        if target < 0 {
            return; // sum exceeded target, stop exploring
        }
        for i in start..candidates.len() {
            current.push(candidates[i]); // add candidate
            backtrack(candidates, target - candidates[i], i, current, results); // recurse with reduced target
            current.pop(); // remove last to backtrack
        }
    }

    let mut results = Vec::new();
    let mut current = Vec::new();
    backtrack(candidates, target, 0, &mut current, &mut results);
    results
}

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

if target == 0 { results.push(current.clone()); return; }

Add current combination to results when sum matches target

if target < 0 { return; }

Stop exploring path if sum exceeds target

for i in start..candidates.len() { current.push(candidates[i]); backtrack(candidates, target - candidates[i], i, current, results); current.pop(); }

Try each candidate starting from 'start', recurse with reduced target, then backtrack

Output

[2, 2, 3]

[7]

Complexity Analysis

Time: O(N^(T/M)) where N is number of candidates, T is target, M is minimum candidate value, because we explore combinations up to target divided by smallest number

Space: O(T/M) for recursion stack and current combination storage, proportional to max depth

vs Alternative: Better than brute force checking all subsets (2^N), because it prunes paths exceeding target early

Edge Cases

Empty candidates list

Returns empty list, no combinations possible

DSA Rust

for i in start..candidates.len() { ... }

Target is zero

Returns list with empty combination [[]]

DSA Rust

if target == 0 { results.push(current.clone()); return; }

Candidates contain duplicates

Duplicates are allowed and can appear multiple times in combinations

DSA Rust

for i in start..candidates.len() { ... }

When to Use This Pattern

When asked to find all combinations of numbers that sum to a target, use backtracking to explore choices and prune paths that exceed the target.

Common Mistakes

Mistake: Not backtracking (not removing last added number) after recursive call
Fix: Always remove last number after recursion to explore other combinations

Mistake: Starting loop from 0 every time causing duplicate combinations
Fix: Start loop from current index to avoid duplicates and maintain order

Summary

Finds all combinations of numbers that add up exactly to a target.

Use when you need every possible group of numbers summing to a value.

The key is to try numbers, reduce target, and backtrack when over or done.

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