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

Recall & Review

beginner

What is the goal of the 'Generate All Combinations Sum K' problem?

To find all unique combinations of numbers from a given list that add up exactly to a target sum K.

beginner

Which algorithmic technique is commonly used to solve 'Generate All Combinations Sum K'?

Backtracking, which tries possible numbers step-by-step and backtracks when the sum exceeds K or no valid combination is found.

intermediate

In backtracking for combinations sum K, why do we sort the input list first?

Sorting helps to stop early when the current number exceeds the remaining sum and avoids duplicate combinations by skipping repeated numbers.

beginner

What is the base case in the recursive backtracking for generating combinations that sum to K?

When the remaining sum is zero, the current combination is valid and should be added to the results.

intermediate

How do you avoid duplicate combinations in 'Generate All Combinations Sum K' when input has repeated numbers?

By skipping numbers that are the same as the previous number at the same recursive depth to prevent generating the same combination multiple times.

What does the backtracking function do when the current sum exceeds K?

A It adds the combination to the result.

B It continues exploring further numbers.

C It resets the sum to zero.

D It stops exploring that path and backtracks.

If the sum exceeds K, no valid combination can be formed by adding more numbers, so backtracking stops exploring that path.

Why is it important to sort the input array before generating combinations?

A To easily skip duplicates and stop early when sum exceeds K.

B To make the output sorted alphabetically.

C To increase the sum of combinations.

D Sorting is not necessary.

Sorting helps to skip duplicates and stop exploring when the current number is greater than the remaining sum.

What is added to the result list when a valid combination is found?

A The sum of the combination.

B The current combination list.

C The index of the last number.

D The original input array.

The current combination of numbers that sum to K is added to the result list.

How do you handle repeated numbers in the input to avoid duplicate combinations?

A Skip the number if it is the same as the previous number at the same recursion level.

B Add all repeated numbers anyway.

C Remove duplicates from the input before processing.

D Ignore the first occurrence of each number.

Skipping repeated numbers at the same recursion depth prevents duplicate combinations.

What happens when the remaining sum becomes zero during backtracking?

A The function restarts from the beginning.

B Backtracking stops completely.

C The current combination is valid and added to the results.

D The sum is reset to the original target.

When remaining sum is zero, it means the current combination sums exactly to K and should be saved.

Explain the backtracking approach to generate all combinations that sum to K.

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

How do you avoid duplicate combinations when the input list contains repeated numbers?

Sorting helps to detect duplicates easily.

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