[LeetCode] 39. Combination Sum ☆☆☆(数组相加等于指定的数)

佚名 6年前 (2019-05-13) 随笔 1775人围观抢沙发百度已收录

https://leetcode.wang/leetCode-39-Combination-Sum.html

描述

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.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

Note:

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

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

解析

回溯法

参考这里) ，就是先向前列举所有情况，得到一个解或者走不通的时候就回溯。和37题有异曲同工之处，也算是回溯法很典型的应用，直接看代码吧。

动态规划

看原文

代码

回溯法

public List<List<Integer>> combinationSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if(remain < 0) return;
    else if(remain == 0) list.add(new ArrayList<>(tempList));
    else{ 
        for(int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i); 
            //找到了一个解或者 remain < 0 了，将当前数字移除，然后继续尝试
            tempList.remove(tempList.size() - 1);
        }
    }
}