友链
姚屹晨

leetcode - [40] Combination Sum II

2020/06/18

问题描述

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.

给你一个正整数数组candidates和目标值target。

使用数组中的元素凑齐target，数组中的元素仅能使用一次，请计算一共有多少中唯一的组合方式？

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

举个例子：

类似题目：

[39] Combination Sum
[90] Subsets II

Update at 2020_0907

来看下示意图：

再来看下完整实现：

class Solution {

    List<List<Integer>> ans = new LinkedList<>();

    private void dfs(int[] cands, int t, LinkedList<Integer> child, int u, int sum, boolean[] used){
        if (sum == t){
            ans.add(new LinkedList<>(child));
            return;
        } else if (sum > t){
            return;
        }

        for (int i = u; i < cands.length; i++){
            if (used[i] || i > 0 && cands[i] == cands[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            child.add(cands[i]);
            dfs(cands, t, child, i + 1, sum + cands[i], used);
            child.removeLast();
            used[i] = false;
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        int n = candidates.length;
        var used = new boolean[n];
        dfs(candidates, target, new LinkedList<>(), 0, 0, used);
        return ans;
    }
}

解法1

说下思路：

首先，避免重复统计，需要对原始数组进行升序排列。

然后，由于原始数组中的元素只能使用一次，所以递归函数中cur = i + 1。

接着，终止条件和 [39] Combination Sum 这道题一致。

最后，为了避免重复统计，需要加个判断，和 [39] Combination Sum 一样。

if (i > cur && num == candidates[i - 1]){
    continue;
}

来看下实现：

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        
        Arrays.sort(candidates);
        List<List<Integer>> ans = new LinkedList<>();
        bt(candidates, target, ans, new LinkedList<>(), 0);
        return ans;
    }
    
    private void bt(int[] candidates, int remain, 
                    List<List<Integer>> ans, LinkedList<Integer> child, int cur){
        
        if (remain == 0){
            ans.add(new LinkedList<>(child));
        } else if (remain < 0){
            return;    
        }
        
        for (int i = cur; i < candidates.length; i++){
            int num = candidates[i];
            if (i > cur && num == candidates[i - 1]){
                continue;
            }
            child.add(num);
            bt(candidates, remain - num, ans, child, i + 1);
            child.removeLast();
        }
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

（转载本站文章请注明作者和出处 姚屹晨-yaoyichen）

Post Directory