LeetCode 40 Combination Sum II

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. 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]
]

Difficulty Medium

Related Problems

[LeetCode 39] Combination Sums

Analysis

This is same as Combination Sum except we can not use the same element multiple times.

Solutions

1. Cpp solution 9ms

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> result;
        vector<int> sol;
        combinationSum2(candidates, 0, target, sol, result);
        return result;
    }

    void combinationSum2(vector<int> &candidates, int start, int target, vector<int> &sol, vector<vector<int>> &result){
        if(target == 0){
            result.push_back(sol);
            return;
        }
        for(int i = start; i < (int)candidates.size() && target >= candidates[i]; ++i){
            if(i == start || candidates[i] != candidates[i - 1]){
                sol.push_back(candidates[i]);
                combinationSum2(candidates, i + 1, target - candidates[i], sol, result);
                sol.pop_back();
            }
        }
    }
};

1. Go solution

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    all := [][]int{}
    sol := []int{}

    combHelper2(candidates, &sol, 0, target, &all)
    return all
}

func combHelper2(candidates []int, sol *[]int, start, target int, all *[][]int) {
    if target == 0 {
        *all = append(*all, append([]int(nil), *sol...))
        return
    }

    for i := start; i < len(candidates) && target >= candidates[i]; i++ {
        if i > start && candidates[i] == candidates[i - 1] {
            continue
        }
        *sol = append(*sol, candidates[i])
        combHelper2(candidates, sol, i + 1, target-candidates[i], all)
        *sol = (*sol)[0 : len(*sol)-1]
    }
}

Reference