Combination Sum Backtracking DSA Solution - Study Chapter | QuizMaker

Combination Sum explained with permutation brute force, optimized reuse-choice backtracking, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 12m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 11: Recursion & Backtracking

Learning Outcome

After this lesson, you should be able to prevent duplicate combinations by keeping a start index.

Problem Statement

Given distinct candidate numbers and a target, return all unique combinations where chosen numbers sum to target. A candidate may be reused.

Input	Output	Why
`candidates = [2,3,6,7], target = 7`	`[[2,2,3],[7]]`	2+2+3 and 7 both reach the target.

Brute Force Approach

Try every ordered sequence. This creates duplicates like [2,3,2] and [3,2,2].

Optimized Approach

Backtrack with a start index. Reuse the same index when a candidate can be picked again, and move forward to avoid reordered duplicates.

Exact Pseudocode

answer = []
path = []
dfs(start, remaining):
  if remaining == 0:
    answer.add(copy(path))
    return
  for i from start to n - 1:
    if candidates[i] <= remaining:
      path.add(candidates[i])
      dfs(i, remaining - candidates[i])
      path.removeLast()
dfs(0, target)
return answer

Reference Code

class Solution:
    def combinationSum(self, candidates, target):
        answer = []
        path = []

        def dfs(start, remaining):
            if remaining == 0:
                answer.append(path[:])
                return

            for i in range(start, len(candidates)):
                if candidates[i] <= remaining:
                    path.append(candidates[i])
                    dfs(i, remaining - candidates[i])
                    path.pop()

        dfs(0, target)
        return answer

class Solution {
public:
    vector<vector<int>> answer;
    vector<int> path;

    void dfs(vector<int>& candidates, int start, int remaining) {
        if (remaining == 0) {
            answer.push_back(path);
            return;
        }

        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] <= remaining) {
                path.push_back(candidates[i]);
                dfs(candidates, i, remaining - candidates[i]);
                path.pop_back();
            }
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, 0, target);
        return answer;
    }
};

class Solution {
    private List<List<Integer>> answer = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, 0, target);
        return answer;
    }

    private void dfs(int[] candidates, int start, int remaining) {
        if (remaining == 0) {
            answer.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] <= remaining) {
                path.add(candidates[i]);
                dfs(candidates, i, remaining - candidates[i]);
                path.remove(path.size() - 1);
            }
        }
    }
}

Sample Dry Run

Step	State	Result
Start	remaining=7, path=[]	Try candidate 2
Reuse 2	path=[2,2], remaining=3	Still allowed because dfs uses i
Pick 3	path=[2,2,3], remaining=0	Copy answer
Try 7	path=[7], remaining=0	Copy answer

Complexity

Measure	Value	Reason
Time	O(number of valid states)	The search tree depends on target and candidate values.
Space	O(target / minCandidate)	The recursion path depth is bounded by repeated use of the smallest candidate.

Edge Cases

Candidates can be reused.
Combinations should be unique by value order.
remaining below 0 should be avoided or pruned.

Interview Checklist

Use start index to prevent reordered duplicates.
Call dfs(i, ...) to allow reuse.
Copy the path when remaining reaches 0.

FAQs

Why call dfs with i instead of i + 1?

Using i allows the same candidate to be reused.

How are duplicates avoided?

The start index keeps combinations in nondecreasing candidate order.

What is the core pattern?

Backtracking with reusable choices.