Combination Sum (Reuse Allowed)

🎯

Combination Sum (Reuse Allowed)

mediumBACKTRACKINGAmazonGoogleFacebook

Imagine you have a set of different coin denominations and want to find all the ways to make a certain amount using any number of coins, including repeats.

💡 This problem asks for all unique combinations of numbers that sum to a target, allowing reuse of elements. Beginners often struggle because it requires exploring many possibilities and managing duplicates carefully.

📋

Problem Statement

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may reuse the same number from candidates an unlimited number of times. The combinations may be returned in any order.

1 ≤ candidates.length ≤ 301 ≤ candidates[i] ≤ 200All elements of candidates are distinct.1 ≤ target ≤ 500

💡

Example

Input"candidates = [2,3,6,7], target = 7"

Output[[2,2,3],[7]]

2+2+3=7 and 7=7 are the only combinations. Reuse of 2 is allowed.

Input"candidates = [2,3,5], target = 8"

Output[[2,2,2,2],[2,3,3],[3,5]]

Multiple combinations sum to 8, including repeated use of 2 and 3.

• Empty candidates array → []
• Target smaller than smallest candidate → []
• Candidates contain one element equal to target → [[that element]]
• Candidates contain elements larger than target → ignore those elements

⚠️

Common Mistakes

Not allowing reuse of the same candidate in recursion

Misses valid combinations that use the same number multiple times

✅ In recursive call, pass current index again instead of index+1

Not pruning recursion when sum exceeds target

Leads to excessive recursion and timeouts

✅ Add condition to return early if current sum > target

Not sorting candidates before pruning

Pruning condition fails to stop early, wasting time

✅ Sort candidates before recursion to enable early break

Modifying path list without backtracking (pop)

Leads to incorrect combinations or runtime errors

✅ Always remove last element after recursive call to backtrack

Not handling empty candidates or target zero properly

May cause errors or incorrect output

✅ Add base cases to handle empty input and zero target

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem structure by exploring all possible combinations without pruning or optimization. It shows the fundamental recursion tree and how combinations build up.

Intuition

Try every candidate repeatedly until the sum reaches or exceeds the target, backtracking when the sum exceeds target.

Algorithm

1. Start from the first candidate and try to include it multiple times until sum exceeds target.
2. If sum equals target, record the current combination.
3. If sum exceeds target, backtrack.
4. Move to the next candidate and repeat.

💡 The recursion tree can be large and confusing at first because it explores many repeated states without pruning.

</>

Code

from typing import List

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    result = []
    def backtrack(start, path, total):
        if total == target:
            result.append(path[:])
            return
        if total > target:
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path, total + candidates[i])
            path.pop()
    backtrack(0, [], 0)
    return result

# Driver code
if __name__ == '__main__':
    print(combinationSum([2,3,6,7], 7))

Line Notes

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:Defines the main function with type hints for clarity and to specify input/output types.

result = []Initialize a list to store all valid combinations found during recursion.

def backtrack(start, path, total):Helper recursive function to explore combinations starting at index 'start', carrying current path and sum total.

if total == target:Base case: if current sum matches target, record a copy of the current combination path.

if total > target:Prune recursion if sum exceeds target to avoid unnecessary exploration.

for i in range(start, len(candidates)):Iterate over candidates starting from 'start' to allow reuse of the same candidate multiple times.

path.append(candidates[i])Choose candidate i and add it to the current path.

backtrack(i, path, total + candidates[i])Recurse with updated sum and path, allowing reuse of candidate i by passing same index.

path.pop()Backtrack by removing last candidate to try next option and explore other combinations.

backtrack(0, [], 0)Initial call to start recursion with empty path and zero sum.

import java.util.*;

public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (target < 0) {
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i, path, result);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum cs = new CombinationSum();
        System.out.println(cs.combinationSum(new int[]{2,3,6,7}, 7));
    }
}

Line Notes

public List<List<Integer>> combinationSum(int[] candidates, int target) {Main method signature returning list of combinations for given candidates and target.

List<List<Integer>> result = new ArrayList<>();Initialize list to store all valid combinations found.

backtrack(candidates, target, 0, new ArrayList<>(), result);Start recursion with empty path and full target.

if (target == 0) {Base case: found valid combination summing exactly to target.

if (target < 0) {Prune recursion when sum exceeds target to avoid unnecessary calls.

for (int i = start; i < candidates.length; i++) {Iterate candidates from 'start' to allow reuse of same candidate multiple times.

path.add(candidates[i]);Choose candidate i and add to current path.

backtrack(candidates, target - candidates[i], i, path, result);Recurse with reduced target and same start index for reuse.

path.remove(path.size() - 1);Backtrack by removing last candidate to explore other options.

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

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

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

int main() {
    Solution sol;
    vector<int> candidates = {2,3,6,7};
    vector<vector<int>> res = sol.combinationSum(candidates, 7);
    for (auto &comb : res) {
        cout << "[";
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i];
            if (i != comb.size() - 1) cout << ",";
        }
        cout << "]\n";
    }
    return 0;
}

Line Notes

void backtrack(vector<int>& candidates, int target, int start, vector<int>& path, vector<vector<int>>& result) {Recursive helper function exploring combinations starting at index 'start'.

if (target == 0) {Base case: found valid combination summing to target.

if (target < 0) return;Prune recursion if sum exceeded target.

for (int i = start; i < candidates.size(); i++) {Iterate candidates from 'start' to allow reuse.

path.push_back(candidates[i]);Choose candidate i and add to path.

backtrack(candidates, target - candidates[i], i, path, result);Recurse with updated target and same start index.

path.pop_back();Backtrack by removing last candidate to try next option.

function combinationSum(candidates, target) {
    const result = [];
    function backtrack(start, path, total) {
        if (total === target) {
            result.push([...path]);
            return;
        }
        if (total > target) return;
        for (let i = start; i < candidates.length; i++) {
            path.push(candidates[i]);
            backtrack(i, path, total + candidates[i]);
            path.pop();
        }
    }
    backtrack(0, [], 0);
    return result;
}

// Test
console.log(combinationSum([2,3,6,7], 7));

Line Notes

function combinationSum(candidates, target) {Defines main function to find combinations.

const result = [];Initialize array to store valid combinations.

function backtrack(start, path, total) {Recursive helper to explore combinations starting at index 'start'.

if (total === target) {Base case: found valid combination summing to target.

if (total > target) return;Prune recursion if sum exceeds target.

for (let i = start; i < candidates.length; i++) {Iterate candidates from 'start' to allow reuse.

path.push(candidates[i]);Choose candidate i and add to path.

backtrack(i, path, total + candidates[i]);Recurse with updated sum and path.

path.pop();Backtrack by removing last candidate to explore other options.

⏱

Complexity

TimeO(N^(T/M + 1)) where N is number of candidates, T is target, M is minimum candidate

SpaceO(T/M) recursion depth and path storage

Each recursive call tries all candidates, and the depth can be up to target divided by smallest candidate, leading to exponential time due to combinatorial explosion.

💡 For example, with 3 candidates and target 7, worst case tries many combinations, which grows very fast exponentially.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is slow; it helps understand the problem before optimizing.

🧠

Backtracking with Sorting and Early Pruning

💡 Sorting candidates allows early stopping when sum exceeds target, reducing unnecessary recursion and improving efficiency by pruning branches early.

Intuition

By sorting, once a candidate exceeds the remaining target, no further candidates need to be tried at that recursion level.

Algorithm

1. Sort candidates in ascending order.
2. Recursively try candidates starting from current index.
3. If candidate exceeds remaining target, break loop to prune.
4. Record combinations when sum equals target.

💡 Sorting helps cut down branches early, making recursion tree smaller and faster to explore.

</>

Code

from typing import List

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    result = []
    def backtrack(start, path, total):
        if total == target:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] + total > target:
                break
            path.append(candidates[i])
            backtrack(i, path, total + candidates[i])
            path.pop()
    backtrack(0, [], 0)
    return result

# Driver code
if __name__ == '__main__':
    print(combinationSum([2,3,6,7], 7))

Line Notes

candidates.sort()Sort candidates to enable early pruning by ascending order.

result = []Initialize list to store valid combinations.

def backtrack(start, path, total):Recursive helper exploring combinations from index 'start'.

if total == target:Base case: found valid combination summing to target.

for i in range(start, len(candidates)):Iterate candidates from 'start' to allow reuse.

if candidates[i] + total > target:If adding candidate exceeds target, break to prune further exploration.

path.append(candidates[i])Choose candidate i and add to path.

backtrack(i, path, total + candidates[i])Recurse with updated sum and path, allowing reuse.

path.pop()Backtrack by removing last candidate to try next option.

backtrack(0, [], 0)Initial call to start recursion.

import java.util.*;

public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target) break;
            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i, path, result);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum cs = new CombinationSum();
        System.out.println(cs.combinationSum(new int[]{2,3,6,7}, 7));
    }
}

Line Notes

Arrays.sort(candidates);Sort candidates to enable pruning by ascending order.

List<List<Integer>> result = new ArrayList<>();Initialize list to store valid combinations.

backtrack(candidates, target, 0, new ArrayList<>(), result);Start recursion with empty path and full target.

if (target == 0) {Base case: found valid combination summing to target.

for (int i = start; i < candidates.length; i++) {Iterate candidates from 'start' to allow reuse.

if (candidates[i] > target) break;If candidate exceeds target, break to prune further exploration.

path.add(candidates[i]);Choose candidate i and add to path.

backtrack(candidates, target - candidates[i], i, path, result);Recurse with updated target and same start index.

path.remove(path.size() - 1);Backtrack by removing last candidate to try next option.

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

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

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> result;
        vector<int> path;
        backtrack(candidates, target, 0, path, result);
        return result;
    }
};

int main() {
    Solution sol;
    vector<int> candidates = {2,3,6,7};
    vector<vector<int>> res = sol.combinationSum(candidates, 7);
    for (auto &comb : res) {
        cout << "[";
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i];
            if (i != comb.size() - 1) cout << ",";
        }
        cout << "]\n";
    }
    return 0;
}

Line Notes

sort(candidates.begin(), candidates.end());Sort candidates to enable pruning by ascending order.

void backtrack(vector<int>& candidates, int target, int start, vector<int>& path, vector<vector<int>>& result) {Recursive helper exploring combinations from index 'start'.

if (target == 0) {Base case: found valid combination summing to target.

for (int i = start; i < candidates.size(); i++) {Iterate candidates from 'start' to allow reuse.

if (candidates[i] > target) break;If candidate exceeds target, break to prune further exploration.

path.push_back(candidates[i]);Choose candidate i and add to path.

backtrack(candidates, target - candidates[i], i, path, result);Recurse with updated target and same start index.

path.pop_back();Backtrack by removing last candidate to try next option.

function combinationSum(candidates, target) {
    candidates.sort((a,b) => a - b);
    const result = [];
    function backtrack(start, path, total) {
        if (total === target) {
            result.push([...path]);
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] + total > target) break;
            path.push(candidates[i]);
            backtrack(i, path, total + candidates[i]);
            path.pop();
        }
    }
    backtrack(0, [], 0);
    return result;
}

// Test
console.log(combinationSum([2,3,6,7], 7));

Line Notes

candidates.sort((a,b) => a - b);Sort candidates to enable pruning by ascending order.

const result = [];Initialize array to store valid combinations.

function backtrack(start, path, total) {Recursive helper exploring combinations from index 'start'.

if (total === target) {Base case: found valid combination summing to target.

for (let i = start; i < candidates.length; i++) {Iterate candidates from 'start' to allow reuse.

if (candidates[i] + total > target) break;If adding candidate exceeds target, break to prune further exploration.

path.push(candidates[i]);Choose candidate i and add to path.

backtrack(i, path, total + candidates[i]);Recurse with updated sum and path.

path.pop();Backtrack by removing last candidate to try next option.

⏱

Complexity

TimeImproved over brute force due to pruning but still exponential in worst case

SpaceO(T/M) recursion depth and path storage

Sorting and pruning reduce branches by stopping exploration early when candidates exceed remaining target, but worst case remains exponential if many combinations exist.

💡 For example, pruning avoids exploring candidates that can't fit, saving time especially with large candidates.

Interview Verdict: Accepted and faster than brute force

This approach is a practical improvement and often acceptable in interviews.

🧠

Backtracking with Frequency Counting (Avoid Duplicates Explicitly)

💡 This approach explicitly tracks how many times each candidate is used, which can help in variants where duplicates matter or to understand combination construction better. It shows a structured way to build combinations by counts.

Intuition

Instead of blindly adding candidates, count how many times each candidate can be used and build combinations accordingly.

Algorithm

1. Sort candidates to handle them in order.
2. For each candidate, try using it 0 to max times without exceeding target.
3. Recurse to next candidate with updated target after using current candidate count times.
4. Record combination when target is zero.

💡 This approach is more structured and can be adapted for problems with limited usage of candidates.

</>

Code

from typing import List

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    result = []
    def backtrack(index, path, target):
        if target == 0:
            result.append(path[:])
            return
        if index == len(candidates) or target < 0:
            return
        max_use = target // candidates[index]
        for count in range(max_use + 1):
            backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)
    backtrack(0, [], target)
    return result

# Driver code
if __name__ == '__main__':
    print(combinationSum([2,3,6,7], 7))

Line Notes

candidates.sort()Sort candidates for ordered processing to maintain consistency.

result = []Initialize list to store valid combinations.

def backtrack(index, path, target):Recursive helper exploring candidates starting at 'index' with current path and remaining target.

if target == 0:Base case: found valid combination summing to target.

if index == len(candidates) or target < 0:Stop recursion if no candidates left or target negative.

max_use = target // candidates[index]Calculate max times current candidate can be used without exceeding target.

for count in range(max_use + 1):Try all counts from 0 to max_use for current candidate.

backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)Recurse to next candidate with updated path and target.

import java.util.*;

public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int target, int index, List<Integer> path, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (index == candidates.length || target < 0) return;
        int maxUse = target / candidates[index];
        for (int count = 0; count <= maxUse; count++) {
            for (int i = 0; i < count; i++) path.add(candidates[index]);
            backtrack(candidates, target - count * candidates[index], index + 1, path, result);
            for (int i = 0; i < count; i++) path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum cs = new CombinationSum();
        System.out.println(cs.combinationSum(new int[]{2,3,6,7}, 7));
    }
}

Line Notes

Arrays.sort(candidates);Sort candidates for ordered processing.

List<List<Integer>> result = new ArrayList<>();Initialize list to store valid combinations.

backtrack(candidates, target, 0, new ArrayList<>(), result);Start recursion with empty path and full target.

if (target == 0) {Base case: found valid combination summing to target.

if (index == candidates.length || target < 0) return;Stop recursion if no candidates left or target negative.

int maxUse = target / candidates[index];Calculate max times current candidate can be used.

for (int count = 0; count <= maxUse; count++) {Try all counts from 0 to maxUse.

for (int i = 0; i < count; i++) path.add(candidates[index]);Add candidate count times to path.

backtrack(candidates, target - count * candidates[index], index + 1, path, result);Recurse to next candidate with updated target.

for (int i = 0; i < count; i++) path.remove(path.size() - 1);Backtrack by removing added candidates.

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

class Solution {
public:
    void backtrack(vector<int>& candidates, int target, int index, vector<int>& path, vector<vector<int>>& result) {
        if (target == 0) {
            result.push_back(path);
            return;
        }
        if (index == candidates.size() || target < 0) return;
        int maxUse = target / candidates[index];
        for (int count = 0; count <= maxUse; count++) {
            for (int i = 0; i < count; i++) path.push_back(candidates[index]);
            backtrack(candidates, target - count * candidates[index], index + 1, path, result);
            for (int i = 0; i < count; i++) path.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> result;
        vector<int> path;
        backtrack(candidates, target, 0, path, result);
        return result;
    }
};

int main() {
    Solution sol;
    vector<int> candidates = {2,3,6,7};
    vector<vector<int>> res = sol.combinationSum(candidates, 7);
    for (auto &comb : res) {
        cout << "[";
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i];
            if (i != comb.size() - 1) cout << ",";
        }
        cout << "]\n";
    }
    return 0;
}

Line Notes

sort(candidates.begin(), candidates.end());Sort candidates for ordered processing.

void backtrack(vector<int>& candidates, int target, int index, vector<int>& path, vector<vector<int>>& result) {Recursive helper exploring candidates starting at 'index'.

if (target == 0) {Base case: found valid combination summing to target.

if (index == candidates.size() || target < 0) return;Stop recursion if no candidates left or target negative.

int maxUse = target / candidates[index];Calculate max times current candidate can be used.

for (int count = 0; count <= maxUse; count++) {Try all counts from 0 to maxUse.

for (int i = 0; i < count; i++) path.push_back(candidates[index]);Add candidate count times to path.

backtrack(candidates, target - count * candidates[index], index + 1, path, result);Recurse to next candidate with updated target.

for (int i = 0; i < count; i++) path.pop_back();Backtrack by removing added candidates.

function combinationSum(candidates, target) {
    candidates.sort((a,b) => a - b);
    const result = [];
    function backtrack(index, path, target) {
        if (target === 0) {
            result.push([...path]);
            return;
        }
        if (index === candidates.length || target < 0) return;
        const maxUse = Math.floor(target / candidates[index]);
        for (let count = 0; count <= maxUse; count++) {
            const newPath = path.concat(Array(count).fill(candidates[index]));
            backtrack(index + 1, newPath, target - count * candidates[index]);
        }
    }
    backtrack(0, [], target);
    return result;
}

// Test
console.log(combinationSum([2,3,6,7], 7));

Line Notes

candidates.sort((a,b) => a - b);Sort candidates for ordered processing.

const result = [];Initialize array to store valid combinations.

function backtrack(index, path, target) {Recursive helper exploring candidates starting at 'index'.

if (target === 0) {Base case: found valid combination summing to target.

if (index === candidates.length || target < 0) return;Stop recursion if no candidates left or target negative.

const maxUse = Math.floor(target / candidates[index]);Calculate max times current candidate can be used.

for (let count = 0; count <= maxUse; count++) {Try all counts from 0 to maxUse.

const newPath = path.concat(Array(count).fill(candidates[index]));Create new path with candidate repeated count times.

backtrack(index + 1, newPath, target - count * candidates[index]);Recurse to next candidate with updated target.

⏱

Complexity

TimeStill exponential, but more structured exploration

SpaceO(T/M) recursion depth and path storage

Trying counts explicitly can reduce some redundant paths by grouping repeated candidates, but worst case remains exponential due to combinatorial possibilities.

💡 This approach is useful for understanding candidate usage limits and can be adapted for variations where usage counts matter.

Interview Verdict: Accepted, useful for variants

This approach is less common but good to know for interview follow-ups or variants.

📊

All Approaches - One-Glance Tradeoffs

💡 The second approach (backtracking with sorting and pruning) is the best balance of clarity and efficiency for interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	Exponential, very large recursion tree	O(T/M) recursion depth	Yes (deep recursion)	Yes	Mention only - never code
2. Backtracking with Sorting and Pruning	Exponential but pruned, much faster in practice	O(T/M) recursion depth	Less likely due to pruning	Yes	Code this approach
3. Backtracking with Frequency Counting	Exponential, structured exploration	O(T/M) recursion depth	Less likely	Yes	Mention if asked about usage limits or duplicates

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and ask about duplicates and reuse.State brute force recursive approach to explore all combinations.Explain sorting and pruning to optimize recursion.Mention alternative approach with frequency counting if asked about usage limits.Code the optimized backtracking with pruning approach.Test with sample and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test & Discuss: 3min. Total ~20min

What the Interviewer Tests

Ability to design backtracking solutions, optimize with pruning, handle recursion carefully, and communicate tradeoffs.

Common Follow-ups

• What if candidates contain duplicates? → Use sorting and skip duplicates.
• What if each candidate can be used only once? → Modify recursion to move to next index without reuse.
• How to return number of combinations instead of list? → Use DP or memoization.
• Can you optimize space? → Use iterative DP for counting combinations.

💡 These follow-ups test your understanding of variations and ability to adapt your solution.

🔍

Pattern Recognition

When to Use

1) Need all combinations or subsets, 2) Sum or target constraint, 3) Reuse of elements allowed, 4) Distinct candidates

Signature Phrases

all unique combinationssum to targetreuse the same number unlimited times

NOT This Pattern When

Problems that require permutations or order matter, or no reuse allowed, are different patterns.

Similar Problems

Combination Sum II - no reuse allowed, candidates may have duplicatesSubset Sum - decision problem variant, yes/no answerCoin Change - count number of combinations, not list them

Practice

1. Consider the following Python code implementing the optimal backtracking solution for Combination Sum III. What is the final value of res after calling combinationSum3(3, 7)?

easy

A. [[1, 2, 4]]

B. [[1, 3, 3]]

C. [[2, 2, 3]]

D. [[1, 2, 3]]

Solution

1. Step 1: Trace backtracking calls for k=3, n=7

   Start from 1, try combinations of size 3 summing to 7. Valid combos are [1,2,4] only because 1+2+4=7.

2. Step 2: Verify no other combos meet criteria

   Other combos like [1,3,3] or [2,2,3] are invalid due to duplicates or sum mismatch.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only [1,2,4] sums to 7 with 3 distinct numbers [OK]

Hint: Only distinct numbers summing to 7 with size 3 is [1,2,4] [OK]

Common Mistakes:

• Including duplicates like [1,3,3]
• Miscounting sum or size

2. Consider the following Python function that counts subsets with sum K using a space-optimized DP approach. What is the output when called with arr = [1, 2, 3, 3] and K = 6?

def count_subsets_space_optimized(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(K, num - 1, -1):
            dp[j] += dp[j - num]
    return dp[K]

print(count_subsets_space_optimized(arr, K))

easy

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0,0,0,0] since dp[0]=1 and K=6.

2. Step 2: Process each number updating dp

   After processing 1: dp = [1,1,0,0,0,0,0] After 2: dp = [1,1,1,1,0,0,0] After first 3: dp = [1,1,1,2,1,1,1] After second 3: dp = [1,1,1,3,2,2,3]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp[6] = 5 subsets sum to 6 [OK]

Hint: Trace dp updates backward to avoid double counting [OK]

Common Mistakes:

• Forgetting to iterate backward in dp array
• Off-by-one errors in dp indices

3. Identify the bug in the following code snippet that generates subsets iteratively:

medium

A. Modifying subsets in place without copying causes all subsets to be identical

B. Extending result inside the loop causes infinite loop

C. Starting result with [[]] misses the empty subset

D. Using append instead of extend on subsets is incorrect

Solution

1. Step 1: Analyze subset modification

   The code appends num directly to subsets in result, modifying them in place.

2. Step 2: Consequence of in-place modification

   All subsets in result end up referencing the same list, causing duplicates and incorrect subsets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct approach copies subsets before adding new elements [OK]

Hint: Always copy subsets before adding new elements [OK]

Common Mistakes:

• Modifying lists in place
• Extending result inside loop without fix
• Wrong initial result value

4. The following backtracking code attempts to generate all subsets of nums. What is the subtle bug causing incorrect output?

medium

A. Using global variable without resetting between calls

B. Not copying the current subset before appending to result causes all subsets to be the same list

C. Base case missing the empty subset

D. Forgetting to pop after including an element causes subsets to accumulate extra elements

Solution

1. Step 1: Analyze base case append

   The code appends path directly without copying, so all appended references point to the same mutable list.

2. Step 2: Consequence of mutation

   As recursion unwinds and path changes, all entries in result reflect the final state of path, causing incorrect subsets.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending a copy (path[:]) fixes the bug [OK]

Hint: Always append a copy of the current path to result [OK]

Common Mistakes:

• Forgetting to pop after append
• Misunderstanding base case inclusion

5. Suppose the problem is modified so that elements can be reused multiple times in the subset (i.e., the subset can contain duplicates). Which modification to the algorithm is necessary to correctly find the largest divisible subset under this new constraint?

hard

A. Modify DP to consider all previous elements including i itself, allowing repeated use, and remove early break

B. Switch to a graph cycle detection algorithm to handle repeated elements

C. Use the same DP approach but allow dp[i] to consider dp[i] itself for reuse, enabling cycles

D. Use a greedy approach picking the largest element repeatedly until no more divisible

Solution

1. Step 1: Understand reuse impact

   Allowing reuse means elements can appear multiple times, so dp must consider extending from the same element multiple times.

2. Step 2: Modify DP logic

   DP inner loop must consider j ≤ i (including i itself) and remove early break because sorted order no longer guarantees divisibility breaks.

3. Step 3: Reject incorrect options

   Greedy fails to find longest chain; graph cycle detection is unnecessary; naive DP without modification misses reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP adjusted for reuse and no early break handles duplicates [OK]

Hint: Reuse requires DP to consider self and no early break [OK]

Common Mistakes:

• Using original DP without changes leads to incorrect results
• Trying greedy approach which fails on complex divisibility
• Confusing graph cycles with DP chains