Combination Sum II

Problem

Given an array candidates (with possible duplicates) and a target, return every unique combination of candidates that sums to target. Each candidate may be used once per combination.

Constraints

• 1 ≤ candidates.length ≤ 100
• 1 ≤ candidates[i] ≤ 50
• 1 ≤ target ≤ 30

Approach — Backtracking

This is a Backtracking problem. The idea: build candidates one choice at a time and abandon a branch the moment it can't lead to a valid answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: exponential worst case.

Solution code

Python

class Solution:
    def combinationSum2(self, candidates, target):
        candidates.sort()
        res = []
        def bt(start, cur, rem):
            if rem == 0:
                res.append(cur[:]); return
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                if candidates[i] > rem:
                    break
                cur.append(candidates[i])
                bt(i + 1, cur, rem - candidates[i])
                cur.pop()
        bt(0, [], target)
        return res

Java

import java.util.*;

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.