LeetCode: Combination Sum II

Challenge Description

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

Each number in candidates 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.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Approach with Depth-First-Search (DFS)

This challenge is a variant of previous one: LeetCode: Combination Sum.

We can use the same algorithm(DFS) to solve it, one difference is we can not use one element multiple times, so we increment the index in next iteration.

Another point need to notice, the exists duplicate elements in input, so we need to use set<vector<int> > vec_set to remove duplicates in result.

class Solution {
  set<vector<int> > vec_set;

public:
  void dfs(vector<int>& candidates, vector<int> path, int start, int target) {
    if(target == 0){
      vec_set.insert(path);
      return;
    }
    for(int k=start; k<candidates.size(); k++) {
      int cur = candidates[k];
      if(cur > target) break;

      int remain = target - cur;
      path.push_back(cur);
      // Note: k+1 is to increment the index in next loop
      dfs(candidates, path, k+1, remain); 
      path.pop_back();
    }
  }

  vector<vector<int> > combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<int> path;
    vector<vector<int> > ans;
    dfs(candidates, path, 0, target);
    for(set<vector<int> >::iterator it = vec_set.begin(); it != vec_set.end(); ++it)
      ans.push_back(*it);

    return ans;
  }
};

Preparing for an interview? Check out this!

Join my Email List for more insights, It's Free!😋

← LeetCode: Reverse Integer LeetCode: Combination Sum →