Woodstock Blog

a tech blog for general algorithmic interview questions

[LeetCode 40] Combination Sum II

Question

link

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

Stats

Frequency 2
Difficulty 4
Adjusted Difficulty 3
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This problem is derived from the “Combination Sum” problem.

The solution is the “Combination Sum” solution plus some duplication avoidance technique.

Solution

Main part of this solution is same as “Combination Sum”. There is only 2 lines of code that needs to be added/modified.

First change, When go into the next recursive call, instead of:

helper(ans, cand, path, i, len, target - cand[i]);

Change it to

helper(ans, cand, path, i + 1, len, target - cand[i]);

Second change, inside the for-loop, instead of getting next element right away, we get the element with different value. The additional code is:

if (i > pos && candidates[i] == candidates[i - 1]) {
    continue;
}

My code

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (candidates == null || candidates.length == 0) {
            return ans;
        }
        Arrays.sort(candidates);
        int len = candidates.length;
        helper(ans, candidates, new ArrayList<Integer>(), 0, len, target);
        return ans;
    }

    private void helper(List<List<Integer>> ans, int[] cand, List<Integer> path, int pos, int len, int target) {
        if (target == 0) {
            ans.add(new ArrayList<Integer>(path));
            return;
        } else if (target < 0) {
            return;
        }
        for (int i = pos; i < len; i++) {
            // if 'i' points to a repeated number, skip.
            if (i > pos && cand[i] == cand[i - 1]) {
                continue;
            }
            // insert cand[i] into path list, and continue search dfs
            path.add(cand[i]);
            helper(ans, cand, path, i + 1, len, target - cand[i]);
            path.remove(path.size() - 1);
        }
    }
}