Combination Sum II

medium array backtracking

Problem

Given a collection of candidate numbers (with duplicates) and a target, find all unique combinations where the candidates sum to target. Each number may be used at most once.

Inputcandidates = [10, 1, 2, 7, 6, 1, 5], target = 8

Output[[1,1,6],[1,2,5],[1,7],[2,6]]

Sort first, then DFS; skip nums[i] when it equals nums[i-1] at the same level.

candidates

target

def combination_sum2(candidates, target):
    candidates.sort()
    out, cur = [], []
    def dfs(start, remain):
        if remain == 0:
            out.append(cur[:]); return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]: continue
            if candidates[i] > remain: break
            cur.append(candidates[i])
            dfs(i + 1, remain - candidates[i])
            cur.pop()
    dfs(0, target)
    return out

function combinationSum2(candidates, target) {
  candidates.sort((a, b) => a - b);
  const out = [], cur = [];
  function dfs(start, remain) {
    if (remain === 0) { out.push(cur.slice()); return; }
    for (let i = start; i < candidates.length; i++) {
      if (i > start && candidates[i] === candidates[i - 1]) continue;
      if (candidates[i] > remain) break;
      cur.push(candidates[i]);
      dfs(i + 1, remain - candidates[i]);
      cur.pop();
    }
  }
  dfs(0, target);
  return out;
}

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> out = new ArrayList<>();
        dfs(candidates, 0, target, new ArrayList<>(), out);
        return out;
    }
    private void dfs(int[] c, int start, int remain, List<Integer> cur, List<List<Integer>> out) {
        if (remain == 0) { out.add(new ArrayList<>(cur)); return; }
        for (int i = start; i < c.length; i++) {
            if (i > start && c[i] == c[i - 1]) continue;
            if (c[i] > remain) break;
            cur.add(c[i]);
            dfs(c, i + 1, remain - c[i], cur, out);
            cur.remove(cur.size() - 1);
        }
    }
}

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& c, int target) {
        sort(c.begin(), c.end());
        vector<vector<int>> out;
        vector<int> cur;
        dfs(c, 0, target, cur, out);
        return out;
    }
    void dfs(vector<int>& c, int start, int remain, vector<int>& cur, vector<vector<int>>& out) {
        if (remain == 0) { out.push_back(cur); return; }
        for (int i = start; i < (int)c.size(); i++) {
            if (i > start && c[i] == c[i - 1]) continue;
            if (c[i] > remain) break;
            cur.push_back(c[i]);
            dfs(c, i + 1, remain - c[i], cur, out);
            cur.pop_back();
        }
    }
};

Explanation

We want every group of numbers that adds up to target, where each number can be used at most once and the candidate list may contain duplicates. The challenge is avoiding the same combination twice.

The first move is to sort the candidates. Sorting lets us do two things: stop early when a number is already bigger than what remains, and easily spot duplicate values sitting next to each other.

The search is a backtracking dfs(start, remain). It tries each candidate from index start onward, subtracts it from remain, and recurses with i + 1 so that number is not reused. When remain hits 0 we record the current path; then we undo the choice and try the next one.

Two pruning rules keep it correct and fast. The line if i > start and candidates[i] == candidates[i-1]: continue skips a repeated value at the same level, which is what stops duplicate combinations. And if candidates[i] > remain: break stops the loop early because everything after is even larger (sorted).

Example: sorted [1,1,2,5,6,7,10], target 8. We pick the first 1, then a second 1, then 6 → [1,1,6]. Back at the top level the second 1 is skipped as a same-level duplicate, so [1,1,6] is never produced again.

Time: O(2ⁿ) Space: O(n)