LintCode 153 Combination Sum II

思路

与combination sum思路基本一致，由于一个数字不能被重复使用，所以需要像Subsets II那题一样去重。

时间复杂度O(2^n)
空间复杂度O(logn)

代码

public class Solution {
    /*** @param num: Given the candidate numbers* @param target: Given the target number* @return: All the combinations that sum to target*/public List<List<Integer>> combinationSum2(int[] num, int target) {
    // write your code hereList<List<Integer>> results = new ArrayList<>();if (num == null) {
    return results;}Arrays.sort(num);dfs(num, 0, target, new ArrayList<>(), results);return results;}private void dfs(int[] nums, int startIndex, int target, List<Integer> combination,List<List<Integer>> results) {
    if (target == 0) {
    results.add(new ArrayList<>(combination));return;} if (target < 0) {
    return;}for (int i = startIndex; i < nums.length; i++) {
    if (i > 0 && nums[i] == nums[i - 1] && i > startIndex) {
    continue;}combination.add(nums[i]);dfs(nums, i + 1, target - nums[i], combination, results);combination.remove(combination.size() - 1);}}
}