LeetCode百题【组合总和】

题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

1 2	`输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]`

示例 3：

1 2	`输入: candidates = [2], target = 1 输出: []`

提示：

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都 互不相同
1 <= target <= 500

解法

深度优先搜索
- 注意题目说当前的数可以重复使用
- dfs分支选择是这道题的精髓

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result=new ArrayList<>();
        List<Integer> combine =new ArrayList<>();
        dfs(candidates, target, result, combine, 0);
        return result;

    }

    /**
     * 深度优先搜索
     * @param candidates 数组
     * @param target 目标值
     * @param result 返回的结果
     * @param combine 中间值 存储单个和为target的list
     * @param index candidates数的下标，表示选择的数
     */
    public void dfs(int[] candidates, int target,List<List<Integer>> result,List<Integer> combine,int index){
        //1.定义递归出口
        if(index==candidates.length){
            return;
        }
        if (target==0){
            //找到一个结果子集，加入result
            result.add(new ArrayList<>(combine));
            return;
        }
        //2.题目要求可以重复选择当前的数，所以可以选择跳过，也可以选择当前的数
        //跳过
        dfs(candidates, target, result, combine, index+1);
        //选择当前的数
        if (target-candidates[index]>=0){
            combine.add(candidates[index]);
            dfs(candidates, target-candidates[index],result,combine,index);
            combine.remove(combine.size()-1);
        }
    }
}