友链
姚屹晨

leetcode - [39] Combination Sum

2020/06/18

问题描述

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

给你一个正整数数组，其中的元素都是唯一的，还有个目标整数target。

使用数组中的元素，不限次数，计算组成target的所有情况。

Note:

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

注意，返回列表中不包含重复的组合。

举个例子：

Update at 2020_0907

来看下示意图：

再来看下实现：

class Solution {

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

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

        for (int i = u; i < cands.length; i++){
            child.add(cands[i]);
            dfs(cands, t, child, sum + cands[i], i);
            child.removeLast();
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target, new LinkedList<>(), 0, 0);
        return ans;
    }
}

解法1

Thanks @issac3

先来看下示意图：

我的想法是这样的：

首先，我们需要哪些东西？

我需要一个存储最终结果的嵌套列表ans，一个临时列表child，还有一个指向数组的索引cur。

再加上题目提供的candidates数组和target目标值。

然后，由于原始数组中元素的使用次数不受限制，所以调用bt()递归函数时，cur仍保持不变，不能加一。

接着，思考一下，递归函数的终止条件是什么？

临时列表child的所有元素之和sum大于target。

或者sum == target，说明我们找到了一个答案。

来看下实现：

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
        List<List<Integer>> ans = new LinkedList<>();
        bt(candidates, target, ans, new LinkedList<>(), 0);
        return ans;
    }
    
    private void bt(int[] candidates, int target, 
                    List<List<Integer>> ans, LinkedList<Integer> child, int cur){
        
        int sum = child.stream().mapToInt(i -> i).sum();
        if (sum == target){
            ans.add(new LinkedList<>(child));
        } else if (sum > target){
            // cur++;
            return;
        }
        
        for (int i = cur; i < candidates.length; i++){
            child.add(candidates[i]);
            bt(candidates, target, ans, child, i);
            child.removeLast();
        }
    }
}

优化一下，我们反向思考，将target减去当前节点值，终止条件同样是两个：

注意喔，target每次遍历都会减去当前节点，所以会不断变小。

当target == 0，说明我们找到了答案。

若target < 0，该层遍历就不需要继续执行了，直接返回到上一层递归。

来看下实现：

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
        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++){
            child.add(candidates[i]);
            bt(candidates, remain - candidates[i], ans, child, i);
            child.removeLast();
        }
    }
}

Enjoy it !


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

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

Post Directory