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. You need to generate all unique groups of size k from numbers 1 to n without repetition, where order within each group does not matter. Which algorithmic approach guarantees generating all such groups efficiently without duplicates?

easy

A. Backtracking that explores all number choices with pruning to avoid duplicates

B. Greedy selection picking the smallest available number until group size is reached

C. Dynamic programming to count subsets but not generate them explicitly

D. Sorting all numbers and then selecting consecutive sequences of length k

Solution

1. Step 1: Understand the problem requires all unique combinations of size k from n numbers

   Greedy or sorting consecutive sequences do not guarantee all unique combinations without duplicates.

2. Step 2: Backtracking with pruning systematically explores all valid combinations and avoids duplicates by controlling start indices

   This approach ensures all unique groups are generated efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking with pruning is the standard approach for combinations [OK]

Hint: Backtracking with pruning avoids duplicates efficiently [OK]

Common Mistakes:

• Thinking greedy or sorting consecutive sequences generate all combinations

3. Consider the following code snippet implementing the trie-based solution for counting valid words for puzzles. Given the words = ["apple", "plea", "plead"] and puzzles = ["aelwxyz"], what is the returned count for this puzzle?

easy

A. [1]

B. [0]

C. [2]

D. [3]

Solution

1. Step 1: Compute bitmasks for words

   "apple" -> letters {a,p,l,e}, mask with ≤7 bits; "plea" and "plead" similarly processed.

2. Step 2: Check puzzle "aelwxyz"

   First letter 'a' must be in word; words "apple" and "plea" contain 'a' and are subsets of puzzle letters; "plead" contains 'd' not in puzzle.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two words match conditions [OK]

Hint: Count words containing puzzle first letter and subset of puzzle letters [OK]

Common Mistakes:

• Counting words missing first letter
• Including words with letters outside puzzle
• Off-by-one in counting matches

4. You need to generate all possible subsets of a given set of distinct integers. Which approach guarantees generating every subset exactly once with a time complexity proportional to the number of subsets times the size of each subset?

easy

A. Greedy algorithm that picks elements based on their value order

B. Enumerate all bitmasks from 0 to 2^n - 1, selecting elements where bits are set

C. Dynamic programming to count subsets without generating them

D. Sorting the array and using two pointers to find pairs

Solution

1. Step 1: Understand the problem

   We want to generate all subsets of a set, which are 2^n in number.

2. Step 2: Identify the approach that enumerates all subsets

   Bitmask enumeration from 0 to 2^n - 1 maps each bit to an element's inclusion, guaranteeing all subsets exactly once.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask enumeration covers all subsets systematically [OK]

Hint: Bitmask from 0 to 2^n-1 enumerates all subsets [OK]

Common Mistakes:

• Thinking greedy or sorting can generate all subsets efficiently

5. The following code attempts to find the largest divisible subset but contains a subtle bug. Identify the line with the bug.

def largestDivisibleSubset(nums):
    if not nums:
        return []
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n
    max_index = 0

    for i in range(n):
        for j in range(i - 1, -1, -1):
            if nums[j] % nums[i] == 0:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            else:
                break
        if dp[i] > dp[max_index]:
            max_index = i

    result = []
    while max_index >= 0:
        result.append(nums[max_index])
        max_index = prev[max_index]
    return result[::-1]

medium

A. Line with 'result.append(nums[max_index])'

B. Line with 'dp = [1] * n'

C. Line with 'max_index = 0'

D. Line with 'if nums[j] % nums[i] == 0:'

Solution

1. Step 1: Check divisibility condition

   The condition should be nums[i] % nums[j] == 0 because we want to check if current number is divisible by a smaller number.

2. Step 2: Understand impact of bug

   Using nums[j] % nums[i] == 0 reverses the divisibility logic, causing incorrect dp updates and wrong subsets.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct divisibility check is crucial for correctness [OK]

Hint: Divisibility check direction matters [OK]

Common Mistakes:

• Swapping divisor and dividend in modulo check
• Not sorting input before DP
• Incorrect subset reconstruction