Generate All Combinations Sum K in DSA Rust - Execution Trace

Concept Flow - Generate All Combinations Sum K

Start with empty combination

↓

Choose next number from candidates

↓

Add number to current combination

↓

Check sum of combination

↓

Save

↓

End when all candidates tried

Build combinations by adding numbers step-by-step, saving when sum equals K, backtracking when sum exceeds K.

Execution Sample

DSA Rust

fn comb_sum_k(candidates: &[i32], k: i32) -> Vec<Vec<i32>> {
    fn backtrack(start: usize, sum: i32, comb: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, candidates: &[i32], k: i32) {
        if sum == k {
            res.push(comb.clone());
            return;
        }
        if sum > k { return; }
        for i in start..candidates.len() {
            comb.push(candidates[i]);
            backtrack(i + 1, sum + candidates[i], comb, res, candidates, k);
            comb.pop();
        }
    }
    let mut res = vec![];
    backtrack(0, 0, &mut vec![], &mut res, candidates, k);
    res
}

Find all unique combinations of numbers that sum to K using backtracking.

Execution Table

Step	Operation	Current Combination	Sum	Action	Visual State
1	Start backtrack at index 0	[]	0	Try candidates[0]=2	[]
2	Add 2	[2]	2	Sum < K, recurse next index 1	[2]
3	Add 3	[2,3]	5	Sum < K, recurse next index 2	[2,3]
4	Add 6	[2,3,6]	11	Sum > K, backtrack	[2,3]
5	Backtrack, remove 6	[2,3]	5	Try next candidate index 3	[2,3]
6	Add 7	[2,3,7]	12	Sum > K, backtrack	[2,3]
7	Backtrack, remove 7	[2,3]	5	No more candidates, backtrack	[2]
8	Backtrack, remove 3	[2]	2	Try next candidate index 2	[2]
9	Add 6	[2,6]	8	Sum < K, recurse next index 3	[2,6]
10	Add 7	[2,6,7]	15	Sum > K, backtrack	[2,6]
11	Backtrack, remove 7	[2,6]	8	No more candidates, backtrack	[2]
12	Backtrack, remove 6	[2]	2	Try next candidate index 3	[2]
13	Add 7	[2,7]	9	Sum == K, save combination	[2,7]
14	Backtrack, remove 7	[2]	2	No more candidates, backtrack	[]
15	Backtrack, remove 2	[]	0	Try next candidate index 1	[]
16	Add 3	[3]	3	Sum < K, recurse next index 2	[3]
17	Add 6	[3,6]	9	Sum == K, save combination	[3,6]
18	Backtrack, remove 6	[3]	3	Try next candidate index 3	[3]
19	Add 7	[3,7]	10	Sum > K, backtrack	[3]
20	Backtrack, remove 7	[3]	3	No more candidates, backtrack	[]
21	Backtrack, remove 3	[]	0	Try next candidate index 2	[]
22	Add 6	[6]	6	Sum < K, recurse next index 3	[6]
23	Add 7	[6,7]	13	Sum > K, backtrack	[6]
24	Backtrack, remove 7	[6]	6	No more candidates, backtrack	[]
25	Backtrack, remove 6	[]	0	Try next candidate index 3	[]
26	Add 7	[7]	7	Sum < K, no more candidates, backtrack	[7]
27	Backtrack, remove 7	[]	0	No more candidates, end	[]

💡 All candidates tried, backtracked fully, all combinations found

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 13	After Step 17	After Step 26	Final
combination	[]	[2]	[2,3]	[2,7]	[3,6]	[7]	[]
sum	0	2	5	9	9	7	0
index	0	1	2	3	3	3	end
results	[]	[]	[]	[[2,7]]	[[2,7],[3,6]]	[[2,7],[3,6]]	[[2,7],[3,6]]

Key Moments - 3 Insights

Why do we backtrack (remove last number) after sum exceeds K?

Because when sum > K (see steps 4,6,10), no further additions can make sum == K, so we remove last number to try other candidates (backtrack).

Why do we increase index when recursing?

To avoid reusing the same number and to ensure combinations are unique, we move to next index (see step 2 to 3, 16 to 17).

How do we save combinations only when sum == K?

At steps 13,17, when sum equals K, we clone and save the current combination to results, ensuring only valid sums are stored.

Visual Quiz - 3 Questions

Look at the execution table at step 13, what is the current combination?

A [6,7]

B [3,6]

C [2,7]

D [2,3]

💡 Hint

Check the 'Current Combination' column at step 13 in the execution table.

At which step does the sum first exceed K?

A Step 3

B Step 4

C Step 13

D Step 17

💡 Hint

Look for the first row where 'Sum' is greater than K in the execution table.

If we allowed reuse of the same candidate index in recursion, how would the execution table change?

A More combinations with repeated numbers would appear

B Fewer combinations would be found

C No change in combinations

D The algorithm would stop immediately

💡 Hint

Consider how allowing the same index multiple times affects combination uniqueness.

Concept Snapshot

Generate All Combinations Sum K:
- Use backtracking to build combinations
- Add numbers stepwise, track sum
- Save combination when sum == K
- Backtrack when sum > K
- Move forward index to avoid repeats

Full Transcript

This concept shows how to find all unique combinations of numbers that add up to a target sum K. We start with an empty combination and try adding each candidate number one by one. If the sum equals K, we save the combination. If the sum exceeds K, we remove the last number and try another. We move forward through the candidate list to avoid duplicates. The execution table traces each step, showing the current combination, sum, and actions taken. Key moments clarify why backtracking is needed and how combinations are saved. The visual quiz tests understanding of the steps and effects of changing recursion rules.

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