Generate All Combinations Sum K in DSA C++

Mental Model

We try all possible groups of numbers that add up to a target sum by exploring choices step-by-step and backtracking when needed.

Analogy: Imagine picking fruits from a basket to make a fruit salad that weighs exactly K grams. You try adding one fruit at a time, and if the total weight goes over K, you remove the last fruit and try a different one.

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

Start:
[] (empty combination)

Try adding 2:
[2]

Try adding 2 again:
[2 -> 2]

Try adding 3:
[2 -> 2 -> 3]

If sum > 7, remove last and try next candidate

Final combinations:
[7]
[2 -> 2 -> 3]

Dry Run Walkthrough

Input: candidates: [2, 3, 6, 7], target sum K = 7

Goal: Find all unique combinations of candidates where the numbers sum to 7. Each number can be used unlimited times.

Step 1: Start with empty combination and first candidate 2

[] (sum=0)

Why: We begin exploring from the first candidate with an empty combination

Step 2: Add 2 to combination

[2] (sum=2)

Why: Try including 2 to move closer to target sum

Step 3: Add 2 again

[2 -> 2] (sum=4)

Why: We can reuse candidates, so try adding 2 again

Step 4: Add 3

[2 -> 2 -> 3] (sum=7)

Why: Adding 3 reaches the target sum exactly

Step 5: Record combination [2, 2, 3] and backtrack by removing last 3

[2 -> 2] (sum=4)

Why: We found a valid combination, now try other options by removing last added number

Step 6: Try next candidate 6 from position after 3

[2 -> 2 -> 6] (sum=10)

Why: Adding 6 exceeds target, so backtrack immediately

Step 7: Backtrack by removing 6 and then 2 to try next candidates

[2] (sum=2)

Why: Remove invalid additions to try other candidates

Step 8: Try candidate 3 from position after 2

[2 -> 3] (sum=5)

Why: Try adding 3 to current combination

Step 9: Add 3 again

[2 -> 3 -> 3] (sum=8)

Why: Sum exceeds target, backtrack by removing last 3

Step 10: Try candidate 6

[2 -> 3 -> 6] (sum=11)

Why: Sum exceeds target, backtrack

Step 11: Backtrack to empty and try candidate 7

[7] (sum=7)

Why: 7 alone matches target sum

Step 12: Record combination [7]

[7]

Why: Found another valid combination

Result:

[2 -> 2 -> 3] -> null
[7] -> null

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void backtrack(const vector<int>& candidates, int target, int start, vector<int>& combination, vector<vector<int>>& results) {
        if (target == 0) {
            results.push_back(combination); // found valid combination
            return;
        }
        if (target < 0) {
            return; // sum exceeded target, stop exploring
        }
        for (int i = start; i < candidates.size(); ++i) {
            combination.push_back(candidates[i]); // choose candidate
            backtrack(candidates, target - candidates[i], i, combination, results); // explore further with updated target
            combination.pop_back(); // backtrack: remove last candidate
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> results;
        vector<int> combination;
        backtrack(candidates, target, 0, combination, results);
        return results;
    }
};

int main() {
    vector<int> candidates = {2, 3, 6, 7};
    int target = 7;
    Solution sol;
    vector<vector<int>> results = sol.combinationSum(candidates, target);
    for (const auto& comb : results) {
        for (int num : comb) {
            cout << num << " ";
        }
        cout << "\n";
    }
    return 0;
}

if (target == 0) { results.push_back(combination); return; }

record combination when sum matches target exactly

if (target < 0) { return; }

stop exploring when sum exceeds target

for (int i = start; i < candidates.size(); ++i) {

iterate candidates starting from current index to avoid duplicates

combination.push_back(candidates[i]);

choose candidate to add to current combination

backtrack(candidates, target - candidates[i], i, combination, results);

explore further with reduced target and same start to allow reuse

combination.pop_back();

backtrack by removing last candidate to try next option

Output

2 2 3 

7 

Complexity Analysis

Time: O(N^(T/M + 1)) where N is number of candidates, T is target, M is minimum candidate value, because we explore all combinations up to target sum

Space: O(T/M) for recursion stack and combination storage, where T is target and M is minimum candidate

vs Alternative: Compared to brute force checking all subsets, this approach prunes paths early when sum exceeds target, saving time

Edge Cases

empty candidates array

returns empty result since no candidates to form combinations

DSA C++

for (int i = start; i < candidates.size(); ++i) {

target is zero

returns one empty combination as valid (sum zero)

DSA C++

if (target == 0) { results.push_back(combination); return; }

candidates contain duplicates

duplicates allowed but combinations generated avoid duplicates by starting from current index

DSA C++

for (int i = start; i < candidates.size(); ++i) {

When to Use This Pattern

When asked to find all combinations of numbers summing to a target with unlimited reuse, use backtracking with pruning to explore choices step-by-step.

Common Mistakes

Mistake: Advancing start index in recursive call causing skipping of valid repeated candidates
Fix: Pass same start index in recursive call to allow reuse of current candidate

Mistake: Not backtracking (not removing last candidate) after recursive call
Fix: Pop last candidate after recursion to restore state for next iteration

Summary

Generates all unique combinations of numbers that sum to a target using backtracking.

Use when you need to find all ways to sum to a number using given candidates with unlimited reuse.

The key is to explore candidates step-by-step, add them, and backtrack when sum exceeds target or after recording valid combinations.

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