组合总和 | 徐年の博客

力扣 39. 组合总和

题目说明

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

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

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

提示：
- 1 <= candidates.length <= 30
- 1 <= candidates[i] <= 200
- candidate 中的每个元素都是独一无二的。
- 1 <= target <= 500

示例

示例 1:

1 2	输入: candidates = [2,3,6,7], target = 7 输出: [[7],[2,2,3]]

示例 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 输出: []

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，采用了回溯的办法，排序以及递归时记录上次添加位置保证顺序选取元素，避免了元素组合的重复出现，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * 数组
     * DFS
     * 回溯
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();

        List<Integer> temp = new ArrayList<>();

        // 排序,只选取顺序的组合
        Arrays.sort(candidates);

        dfs(result, temp, candidates, target, 0);

        return result;
    }

    /**
     * result 结果集
     * temp 暂存的序列
     * candidates 原数组
     * target 目标值
     * tick 标记当前遍历到的元素,保证每次只会按顺序组合,比如只会有2,2,3 而不会出现3,2,2
     */
    public void dfs(List<List<Integer>> result, List<Integer> temp, int[] candidates, int target, int tick) {
        // 组合成功
        if (target == 0) {
            result.add(temp);
            return ;
        }

        // 临时数组和超过目标值
        if (target < candidates[tick]) {
            return ;
        }

        for (int i = tick; i < candidates.length && candidates[i] <= target; i++) {
            // 拷贝数组,所以就不用回溯了
            List<Integer> list = new ArrayList<>(temp);
            list.add(candidates[i]);
            dfs(result, list, candidates, target - candidates[i], i);
        }
    }
}