Generate All Combinations Sum K in DSA C++ - Execution Trace

Concept Flow - Generate All Combinations Sum K

Start with empty combination

↓

Pick next number from candidates

↓

Add number to current combination

↓

Check sum of combination

↓

Save

↓

Backtrack: remove last number

↓

Try next candidate

↓

End when all candidates tried

Start with an empty list, pick numbers one by one, add them if sum is less or equal to K, save if sum equals K, backtrack to try other combinations.

Execution Sample

DSA C++

void backtrack(int start, int k, vector<int>& comb, vector<vector<int>>& res) {
  if (k == 0) { res.push_back(comb); return; }
  for (int i = start; i < candidates.size(); i++) {
    if (candidates[i] > k) break;
    comb.push_back(candidates[i]);
    backtrack(i, k - candidates[i], comb, res);
    comb.pop_back();
  }
}

This code finds all combinations of numbers that sum to K by trying candidates recursively and backtracking.

Execution Table

Step	Operation	Current Combination	Remaining Sum (k)	Action	Visual State
1	Start backtrack(0, 7, [], [])	[]	7	Begin search	[]
2	Pick candidate 2	[2]	5	Add 2 to combination	[2]
3	Pick candidate 2 again	[2, 2]	3	Add 2 again	[2 -> 2]
4	Pick candidate 2 again	[2, 2, 2]	1	Add 2 again	[2 -> 2 -> 2]
5	Candidate 3 > remaining 1	[2, 2, 2]	1	Skip candidate 3	[2 -> 2 -> 2]
6	Pick candidate 4	[2, 2, 2, 4]	-3	Add 4, sum exceeded	[2 -> 2 -> 2 -> 4]
7	Backtrack, remove 4	[2, 2, 2]	1	Remove last number	[2 -> 2 -> 2]
8	Backtrack, remove 2	[2, 2]	3	Remove last number	[2 -> 2]
9	Pick candidate 3	[2, 2, 3]	0	Add 3, sum reached	[2 -> 2 -> 3]
10	Save combination	[2, 2, 3]	0	Save [2,2,3]	[2 -> 2 -> 3]
11	Backtrack, remove 3	[2, 2]	3	Remove last number	[2 -> 2]
12	Candidate 4 > remaining 3	[2, 2]	3	Skip candidate 4	[2 -> 2]
13	Backtrack, remove 2	[2]	5	Remove last number	[2]
14	Pick candidate 3	[2, 3]	2	Add 3	[2 -> 3]
15	Candidate 3 > remaining 2	[2, 3]	2	Skip candidate 3	[2 -> 3]
16	Candidate 4 > remaining 2	[2, 3]	2	Skip candidate 4	[2 -> 3]
17	Backtrack, remove 3	[2]	5	Remove last number	[2]
18	Pick candidate 4	[2, 4]	1	Add 4	[2 -> 4]
19	Candidate 4 > remaining 1	[2, 4]	1	Skip candidate 4	[2 -> 4]
20	Backtrack, remove 4	[2]	5	Remove last number	[2]
21	Backtrack, remove 2	[]	7	Remove last number	[]
22	Pick candidate 3	[3]	4	Add 3	[3]
23	Pick candidate 3	[3, 3]	1	Add 3	[3 -> 3]
24	Candidate 3 > remaining 1	[3, 3]	1	Skip candidate 3	[3 -> 3]
25	Candidate 4 > remaining 1	[3, 3]	1	Skip candidate 4	[3 -> 3]
26	Backtrack, remove 3	[3]	4	Remove last number	[3]
27	Pick candidate 4	[3, 4]	0	Add 4, sum reached	[3 -> 4]
28	Save combination	[3, 4]	0	Save [3,4]	[3 -> 4]
29	Backtrack, remove 4	[3]	4	Remove last number	[3]
30	Backtrack, remove 3	[]	7	Remove last number	[]
31	Pick candidate 4	[4]	3	Add 4	[4]
32	Candidate 4 > remaining 3	[4]	3	Skip candidate 4	[4]
33	Backtrack, remove 4	[]	7	Remove last number	[]
34	End	[]	7	All candidates tried	[]

💡 All candidates tried and all combinations found or skipped due to sum exceeding K

Variable Tracker

Variable	Start	After Step 2	After Step 9	After Step 13	After Step 22	After Step 27	Final
combination	[]	[2]	[2, 2, 3]	[2]	[3]	[3, 4]	[]
remaining sum (k)	7	5	0	5	4	0	7
result (res)	[]	[]	[[2,2,3]]	[[2,2,3]]	[[2,2,3]]	[[2,2,3],[3,4]]	[[2,2,3],[3,4]]

Key Moments - 3 Insights

Why do we backtrack by removing the last number after recursion?

Because after exploring combinations including that number, we must remove it to try other candidates. See steps 10 to 11 and 28 to 29 in execution_table where we save then remove last number.

Why do we stop exploring when candidate > remaining sum?

Because candidates are sorted, any larger number will also exceed sum. See step 5 where candidate 3 is skipped since 3 > remaining 1.

How do we know when to save a combination?

When remaining sum reaches zero, meaning current combination sums exactly to K. See steps 9 and 27 where sum is 0 and combination is saved.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the current combination?

A [3, 4]

B [2, 3]

C [2, 2, 3]

D [2, 2, 2]

💡 Hint

Check the 'Current Combination' column at step 9 in execution_table.

At which step does the algorithm first save a valid combination?

A Step 27

B Step 10

C Step 13

D Step 34

💡 Hint

Look for 'Save combination' action in execution_table.

If the candidate list included 1, how would the variable 'remaining sum (k)' change after step 2?

A It would decrease by 1 instead of 2

B It would stay the same

C It would increase

D It would become zero

💡 Hint

See variable_tracker for how 'remaining sum (k)' changes when adding candidates.

Concept Snapshot

Generate All Combinations Sum K:
- Use backtracking to build combinations.
- Add candidates if sum <= K.
- Save combination if sum == K.
- Backtrack by removing last added number.
- Candidates sorted to prune search early.
- Explore all combinations recursively.

Full Transcript

This concept shows how to generate all combinations of numbers that add up to a target sum K. We start with an empty combination and try adding candidates one by one. If the sum of the combination equals K, we save it. If the sum is less than K, we continue adding more numbers recursively. If the sum exceeds K, we stop exploring that path. After each recursive call, we remove the last number to try other candidates. The candidates are sorted to allow early stopping when a candidate is larger than the remaining sum. The execution table traces each step, showing the current combination, remaining sum, and actions like adding, saving, or backtracking. The variable tracker shows how the combination and remaining sum change over time. Key moments clarify why backtracking is needed, when to save combinations, and why we skip candidates that exceed the remaining sum. The visual quiz tests understanding of these steps. This method ensures all valid combinations summing to K are found efficiently.

Practice

1. What is the main goal of the Generate All Combinations Sum K problem?

easy

A. Count the total number of elements in an array

B. Find all unique combinations of numbers that add up to a target sum K

C. Find the maximum number in an array

D. Sort an array of numbers in ascending order

Solution

1. Step 1: Understand the problem goal

   The problem asks to find all unique sets of numbers that add up exactly to a given sum K.

2. Step 2: Differentiate from other tasks

   Sorting, finding max, or counting elements do not involve finding combinations that sum to K.

3. Final Answer:

   Find all unique combinations of numbers that add up to a target sum K -> Option B

4. Quick Check:

   Goal = Find combinations summing to K [OK]

Hint: Focus on combinations that sum exactly to K [OK]

Common Mistakes:

• Confusing sum with sorting
• Looking for max instead of combinations
• Counting elements instead of combinations

2. Which of the following C++ function signatures is correct for a recursive function that generates all combinations summing to K from a vector of integers named candidates?

easy

A. void findCombinations(int index, int target, vector<int>& candidates, vector<int>& current, vector& result)

B. int findCombinations(vector<int> candidates, int target, int index, vector<int> current, vector result)

C. void findCombinations(vector<int> candidates, int target, vector<int> current, vector result)

D. vector<int> findCombinations(int target, vector<int> candidates)

Solution

1. Step 1: Check parameter passing and types

   void findCombinations(int index, int target, vector<int>& candidates, vector<int>& current, vector& result) uses references for vectors to avoid copying and includes all needed parameters: index, target, candidates, current combination, and result container.

2. Step 2: Identify correct return type and parameters

   void findCombinations(int index, int target, vector<int>& candidates, vector<int>& current, vector& result) returns void because it modifies result by reference. Other options either return wrong types or pass vectors by value causing inefficiency.

3. Final Answer:

   void findCombinations(int index, int target, vector<int>& candidates, vector<int>& current, vector& result) -> Option A

4. Quick Check:

   Correct signature uses references and void return [OK]

Hint: Use references to avoid copying large vectors [OK]

Common Mistakes:

• Passing vectors by value causing slow code
• Wrong return type for recursive helper
• Missing index parameter to track position

3. What is the output of the following C++ code snippet that generates all combinations summing to 5 from candidates {1, 2, 3}?

vector<int> candidates = {1, 2, 3};
vector result;
vector<int> current;
findCombinations(0, 5, candidates, current, result);
for (auto &comb : result) {
    for (int num : comb) cout << num << ' ';
    cout << '\n';
}

medium

A. No output

B. 1 2 3
2 3
1 1 3

C. 1 1 1 1 1
2 2 1
3 2

D. 1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
2 3

Solution

1. Step 1: Understand combinations summing to 5

   Possible combinations using {1,2,3} that sum to 5 include: - 1+1+1+1+1 - 1+1+1+2 - 1+1+3 - 1+2+2 - 2+3

2. Step 2: Verify output matches these combinations

   1 1 1 1 1 1 1 1 2 1 1 3 1 2 2 2 3 lists all these combinations correctly, each on a new line, matching expected output.

3. Final Answer:

   1 1 1 1 1 1 1 1 2 1 1 3 1 2 2 2 3 -> Option D

4. Quick Check:

   All valid combos summing to 5 listed [OK]

Hint: List all combos adding to K stepwise [OK]

Common Mistakes:

• Missing some valid combinations
• Including combinations that exceed sum
• Printing duplicates or unordered results

4. Identify the bug in this recursive function snippet for generating combinations summing to K:

void findCombinations(int index, int target, vector<int>& candidates, vector<int>& current, vector& result) {
    if (target == 0) {
        result.push_back(current);
        return;
    }
    for (int i = index; i < candidates.size(); i++) {
        if (candidates[i] <= target) {
            current.push_back(candidates[i]);
            findCombinations(i + 1, target - candidates[i], candidates, current, result);
            current.pop_back();
        }
    }
}

medium

A. The recursive call should use 'i' instead of 'i + 1' to allow repeated elements

B. The base case should check if target < 0 instead of target == 0

C. The function should return an int instead of void

D. The loop should start from 0 instead of index

Solution

1. Step 1: Analyze recursive call for repeated elements

   Using 'i + 1' moves to next candidate, disallowing reuse of the same element multiple times.

2. Step 2: Correct recursive call to allow repeats

   Changing recursive call to use 'i' allows the same element to be chosen multiple times, which is needed for combinations sum problems allowing repeats.

3. Final Answer:

   The recursive call should use 'i' instead of 'i + 1' to allow repeated elements -> Option A

4. Quick Check:

   Use 'i' to allow repeats [OK]

Hint: Use same index in recursion to allow repeats [OK]

Common Mistakes:

• Incrementing index disallows repeated elements
• Wrong base case condition
• Incorrect return type for recursive helper

5. Given candidates {2, 3, 6, 7} and target sum 7, which of the following is the correct set of all unique combinations where numbers can be chosen unlimited times to sum to 7?

hard

A. [[2, 2, 2, 1], [7]]

B. [[7], [3, 3, 1]]

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

D. [[6, 1], [2, 5]]

Solution

1. Step 1: Identify valid combinations summing to 7

   From candidates {2,3,6,7}, valid combinations with unlimited repeats are: - [7] - [2, 2, 3] (2+2+3=7)

2. Step 2: Check options for correctness

   [[7], [2, 2, 3]] lists these exact combinations. Others include invalid numbers like 1 or 5 which are not in candidates.

3. Final Answer:

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

4. Quick Check:

   Only valid combos from candidates listed [OK]

Hint: Sum candidates repeatedly to reach target [OK]

Common Mistakes:

• Including numbers not in candidates
• Ignoring unlimited repeats
• Missing valid combinations