[Leetcode](Leetcode: 39. 组合总和)

题目描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]

示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

思路

思路1 回溯

将题目看成回溯，每次可以从排序后的候选中选择一个数字，如最后满足条件则加入结果中。同时也可以看作是DFS过程，每个节点有从当前值到最后值的叶子
节点，然后DFS实现，其实也可以BFS

代码

代码1

class Solution {
    List> results;
    public List> combinationSum(int[] candidates, int target) {
        results = new ArrayList<>();
        if(candidates == null || candidates.length == 0){
            return results;
        }
        Arrays.sort(candidates);
        List result = new ArrayList<>();
        trackback(candidates, 0, target, result);
        return results;
    }

    private void trackback(int[] candidates, int idx, int target, List result){
        if (target == 0){
            this.results.add(new ArrayList<>(result));
        }
        for(int i = idx; i < candidates.length; i++){
            if (candidates[i] > target){
                break;
            }
            result.add(candidates[i]);
            trackback(candidates, i, target - candidates[i], result);
            result.remove(result.size() - 1);
        }
    }
}