# Question

Formatted question description: https://leetcode.ca/all/40.html

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

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

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]


Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]


Constraints:

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

# Algorithm

Based on Combination_Sum_I, add sorting to move duplicated numbers together and skip.

# Code

• import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Combination_Sum_II {

class Solution {

List<List<Integer>> result = new ArrayList<>();

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if (candidates == null || candidates.length == 0) {
return result;
}

// nlogn
Arrays.sort(candidates);

dfs(candidates, target, 0, new ArrayList<Integer>());

return result;
}

private void dfs(int[] candidates, int target, int start, ArrayList<Integer> onePath) {

if (target < 0) { // target<0, assumption is all positive
return;
}

if (target == 0) {
// continue, and possible 1,-1 are next ones
}

for (int i = start; i < candidates.length; i++) {
if (i > start && candidates[i] == candidates[i - 1]) continue;
dfs(candidates, target - candidates[i], i+1, onePath); // i+1, to use only once
onePath.remove(onePath.size() - 1);
}
}
}

// https://leetcode.com/problems/combination-sum-ii/solution/
// official solution got "Time Limit Exceeded" error, funny but still a good idea solving this problem
class Solution_lc {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
// container to hold the final combinations
List<List<Integer>> results = new ArrayList<>();

HashMap<Integer, Integer> counter = new HashMap<>();
for (int candidate : candidates) {
if (counter.containsKey(candidate))
counter.put(candidate, counter.get(candidate) + 1);
else
counter.put(candidate, 1);
}

// convert the counter table to a list of (num, count) tuples
List<int[]> counterList = new ArrayList<>();
counter.forEach((key, value) -> {
});

backtrack(comb, target, 0, counterList, results);
return results;
}

int remain, int curr,
List<int[]> counter,
List<List<Integer>> results) {

if (remain == 0) {
// make a deep copy of the current combination.
return;
}

for (int nextCurr = curr; nextCurr < counter.size(); ++nextCurr) {
int[] entry = counter.get(nextCurr);
Integer candidate = entry[0], freq = entry[1];

if (freq <= 0)
continue;

// add a new element to the current combination
counter.set(nextCurr, new int[]{candidate, freq - 1});

// continue the exploration with the updated combination
backtrack(comb, remain - candidate, nextCurr, counter, results);

// backtrack the changes, so that we can try another candidate
counter.set(nextCurr, new int[]{candidate, freq});
comb.removeLast();
}
}
}
}

############

class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private int[] candidates;
private int target;

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
this.target = target;
this.candidates = candidates;
dfs(0, 0);
return ans;
}

private void dfs(int i, int s) {
if (s > target) {
return;
}
if (s == target) {
return;
}
for (int j = i; j < candidates.length; ++j) {
if (j > i && candidates[j] == candidates[j - 1]) {
continue;
}
dfs(j + 1, s + candidates[j]);
t.remove(t.size() - 1);
}
}
}

• // OJ: https://leetcode.com/problems/combination-sum-ii/
// Time: O(N^2)
// Space: O(N)
class Solution {
vector<vector<int>> ans;
void dfs(vector<int> &A, int target, int start, vector<int> &tmp) {
if (!target) {
ans.push_back(tmp);
return;
}
for (int i = start; i < A.size() && target >= A[i]; ++i) {
if (i != start && A[i] == A[i - 1]) continue;
tmp.push_back(A[i]);
dfs(A, target - A[i], i + 1, tmp);
tmp.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& A, int target) {
sort(A.begin(), A.end());
vector<int> tmp;
dfs(A, target, 0, tmp);
return ans;
}
};

• class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(i, s):
if s > target:
return
if s == target:
ans.append(t.copy())
return
for j in range(i, len(candidates)):
if j > i and candidates[j] == candidates[j - 1]:
continue
t.append(candidates[j])
dfs(j + 1, s + candidates[j])
t.pop()

ans = []
candidates.sort()
t = []
dfs(0, 0)
return ans

############

class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""

def dfs(nums, target, start, visited, path, res):
if target == 0:
res.append(path + [])
return

for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
if target - nums[i] < 0:
return 0
if i not in visited:
path.append(nums[i])
dfs(nums, target - nums[i], i + 1, visited, path, res)
path.pop()

candidates.sort()
res = []
visited = set([])
dfs(candidates, target, 0, visited, [], res)
return res


• func combinationSum2(candidates []int, target int) (ans [][]int) {
sort.Ints(candidates)
t := []int{}
var dfs func(i, s int)
dfs = func(i, s int) {
if s > target {
return
}
if s == target {
cp := make([]int, len(t))
copy(cp, t)
ans = append(ans, cp)
return
}
for j := i; j < len(candidates); j++ {
if j > i && candidates[j] == candidates[j-1] {
continue
}
t = append(t, candidates[j])
dfs(j+1, s+candidates[j])
t = t[:len(t)-1]
}
}
dfs(0, 0)
return
}

• function combinationSum2(candidates: number[], target: number): number[][] {
candidates.sort((a, b) => a - b);
const n = candidates.length;
const t: number[] = [];
const res: number[][] = [];
const dfs = (i: number, sum: number) => {
if (sum > target) {
return;
}
if (sum === target) {
res.push([...t]);
return;
}
for (let j = i; j < n; j++) {
const num = candidates[j];
if (j > i && num === candidates[j - 1]) {
continue;
}
t.push(num);
dfs(j + 1, sum + num);
t.pop();
}
};
dfs(0, 0);
return res;
}


• /**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function (candidates, target) {
candidates.sort((a, b) => a - b);
const n = candidates.length;
const t = [];
const ans = [];
const dfs = (i, s) => {
if (s > target) {
return;
}
if (s === target) {
ans.push([...t]);
return;
}
for (let j = i; j < n; j++) {
const num = candidates[j];
if (j > i && num === candidates[j - 1]) {
continue;
}
t.push(num);
dfs(j + 1, s + num);
t.pop();
}
};
dfs(0, 0);
return ans;
};


• public class Solution {
public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
Array.Sort(candidates);
var ans = new List<IList<int>>();
var t = new List<int>();
dfs(candidates, 0, 0, target, t, ans);
return ans;
}

private void dfs(int[] candidates, int i, int s, int target, IList<int> t, IList<IList<int>> ans) {
if (s > target) {
return;
}
if (s == target) {
return;
}
for (int j = i; j < candidates.Length; ++j) {
if (j > i && candidates[j] == candidates[j - 1]) {
continue;
}
dfs(candidates, j + 1, s + candidates[j], target, t, ans);
t.RemoveAt(t.Count - 1);
}
}
}

• impl Solution {
fn dfs(i: usize, count: i32, candidates: &Vec<i32>, t: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
if count < 0 {
return;
}
if count == 0 {
res.push(t.clone());
return;
}
for j in i..candidates.len() {
if j > i && candidates[j] == candidates[j - 1] {
continue;
}
let num = candidates[j];
t.push(num);
Self::dfs(j + 1, count - num, candidates, t, res);
t.pop();
}
}

pub fn combination_sum2(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
candidates.sort();
let mut res = Vec::new();
Self::dfs(0, target, &candidates, &mut vec![], &mut res);
res
}
}