Generate All Combinations Sum K in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of combinations summing to K

What is the output of the following C++ code that generates all combinations of numbers from 1 to 4 that sum to 5?

DSA C++

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

void backtrack(int start, int k, int target, vector<int>& current, vector<vector<int>>& result) {
    if (target == 0 && current.size() == k) {
        result.push_back(current);
        return;
    }
    if (target < 0 || current.size() > k) return;
    for (int i = start; i <= 4; ++i) {
        current.push_back(i);
        backtrack(i + 1, k, target - i, current, result);
        current.pop_back();
    }
}

int main() {
    int k = 2, target = 5;
    vector<vector<int>> result;
    vector<int> current;
    backtrack(1, k, target, current, result);
    for (auto& comb : result) {
        for (int num : comb) cout << num << " ";
        cout << "\n";
    }
    return 0;
}

A [[1,4],[2,3]]

B [[1,4],[2,3],[5]]

C [[1,4],[2,3],[1,2,2]]

D [[1,4],[3,2]]

💡 Hint

Focus on combinations of exactly 2 numbers that sum to 5 using numbers 1 to 4 without repetition.

The code finds all combinations of length 2 from numbers 1 to 4 that sum to 5. These are [1,4] and [2,3]. Option A includes 5 alone which is invalid since k=2. Option A includes a triple which is invalid. Option A repeats [3,2] which is same as [2,3] but order matters here and duplicates are avoided.

🧠 Conceptual

intermediate

Number of combinations for sum K with length constraint

Given numbers from 1 to 5, how many unique combinations of length 3 sum to 7?

A 3

B 4

C 5

D 6

💡 Hint

Try to list all combinations of 3 numbers from 1 to 5 that add up to 7.

Allowing repetition of numbers, the unique combinations (in non-decreasing order) of length exactly 3 from 1 to 5 summing to 7 are [1,1,5], [1,2,4], [1,3,3], and [2,2,3]. There are 4 such combinations.

🔧 Debug

advanced

Identify the error in combination sum code

What error does the following code produce when trying to generate all combinations of length k that sum to target?

DSA C++

#include <vector>
using namespace std;

void backtrack(int start, int k, int target, vector<int>& current, vector<vector<int>>& result) {
    if (target == 0 && current.size() == k) {
        result.push_back(current);
        return;
    }
    if (target < 0 || current.size() > k) return;
    for (int i = start; i <= 5; ++i) {
        current.push_back(i);
        backtrack(i, k, target - i, current, result);
        current.pop_back();
    }
}

int main() {
    vector<vector<int>> result;
    vector<int> current;
    backtrack(1, 3, 7, current, result);
    return 0;
}

A No output because base case never reached

B Compilation error due to missing headers

C Infinite recursion leading to stack overflow

D Runtime error due to out of range access

💡 Hint

Check the recursive call's start parameter and how it affects the loop.

The recursive call uses 'backtrack(i, ...)' instead of 'backtrack(i + 1, ...)'. This causes the same number to be reused infinitely, leading to infinite recursion and stack overflow.

📝 Syntax

advanced

Identify syntax error in combination sum code snippet

Which option contains the correct syntax to define a backtracking function that generates combinations of length k summing to target?

A void backtrack(int start, int k, int target, vector<int>& current, vector<vector<int>>& result) { ... }

B void backtrack(int start, int k, int target, vector<int> current, vector<vector<int>> result) { ... }

C void backtrack(int start, int k, int target, vector<int>& current, vector<vector<int>> result) { ... }

D void backtrack(int start, int k, int target, vector<int> current, vector<vector<int>>& result) { ... }

💡 Hint

Consider which parameters need to be passed by reference to reflect changes outside the function.

The current combination vector and the result vector must be passed by reference to avoid copying and to allow modifications to persist. Option A correctly passes both by reference.

🚀 Application

expert

Find all unique combinations summing to K with duplicates allowed

Given the numbers [2,3,6,7], which option correctly outputs all unique combinations where numbers can be chosen multiple times to sum to 7?

DSA C++

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

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

int main() {
    vector<int> candidates = {2,3,6,7};
    vector<vector<int>> result;
    vector<int> current;
    backtrack(0, 7, candidates, current, result);
    for (auto& comb : result) {
        for (int num : comb) cout << num << " ";
        cout << "\n";
    }
    return 0;
}

A [[7],[6,1]]

B [[2,3,2],[7]]

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

D [[2,2,3],[7]]

💡 Hint

Numbers can be reused, but combinations should be unique and sorted by construction.

The code allows reuse of numbers by calling backtrack(i, ...). It generates combinations [2,2,3] and [7]. Option D has different order but same numbers, option D duplicates combinations, option D includes invalid combination with 1 which is not in candidates.

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