[LeetCode Solution 40]: Combination Sum II

[LeetCode Solution 40]: Combination Sum II

*********************************************************************************

Question:

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

--------------------------------------------------------------------------------------------------

Approach Recursive Method

Strategy

The idea is same with the [LeetCode Solution 39] Combination Sum, using backtracking method, but the only difference is how to get the value that we have to skip that can help us to avoid the duplication. Here is an example that gives you the idea:

For example:

We are going to deal the array \([1, 2, 2', 3, 5]\) and the target is \(7\) if we check the tree as the follows, we find that the blue branch and the green branch is doing the same stuff. 

So, how can we find the node that we want to skip, for example, we want to skip the green 2', not the blue 2'. We find that we have to add 2 constraints.

1. When we find that the element adjacent are equal, candidnate[i] == candidnate[i-1];
2. when the index of the element we visit is bigger than the start one. For example, the in example above, green 2' is visited after all the elements in blue 2 have been visited (the 1's 2nd turn to visited the green 2')

The modified code is as follows:

Java

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

 public void helper(int[] candidates, int tar, int start, List<List<Integer>> res, List<Integer> temp) {
  if (tar < 0)
   return;
  else if (tar == 0)
   res.add(new ArrayList<>(temp));
  else {
   for (int i = start; i < candidates.length; i++) {
    if (candidates[i] > tar)
     break;
    if(i > start && candidates[i] == candidates[i-1]) continue; 
    temp.add(candidates[i]);
    helper(candidates, tar - candidates[i], i + 1, res, temp);
    temp.remove(temp.size() - 1);
   }
  }
 }
}

Complexity Analysis

• Time complexity : \(O(2^n)\). where \(n\) is the number of elements in the array. Because we have to try all the \(n\) combinations
• Space complexity : \(O(log(n))\). The space complexity is related to the height of the 'Tree' which is \(O(log(n))\)

The Running results: