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) {
                result.add(new ArrayList<>(onePath));
                // 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;
                onePath.add(candidates[i]);
                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<>();
            LinkedList<Integer> comb = new LinkedList<>();

            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) -> {
                counterList.add(new int[]{key, value});
            });

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

        private void backtrack(LinkedList<Integer> comb,
                               int remain, int curr,
                               List<int[]> counter,
                               List<List<Integer>> results) {

            if (remain == 0) {
                // make a deep copy of the current combination.
                results.add(new ArrayList<Integer>(comb));
                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
                comb.addLast(candidate);
                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) {
            ans.add(new ArrayList<>(t));
            return;
        }
        for (int j = i; j < candidates.length; ++j) {
            if (j > i && candidates[j] == candidates[j - 1]) {
                continue;
            }
            t.add(candidates[j]);
            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:
          visited.add(i)
          path.append(nums[i])
          dfs(nums, target - nums[i], i + 1, visited, path, res)
          path.pop()
          visited.discard(i)

    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) {
            ans.Add(new List<int>(t));
            return;
        }
        for (int j = i; j < candidates.Length; ++j) {
            if (j > i && candidates[j] == candidates[j - 1]) {
                continue;
            }
            t.Add(candidates[j]);
            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
    }
}

40 - Combination Sum II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions