题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

题目分析

组合，本质是单向的排列。
在 DFS 时增加参数 index 表示当前数字的位置，保证后续只向右（>=index）不向左即可。

Java

private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> list = new ArrayList<>();
private int sum = 0;

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

private void dfs(int[] candidates, int target, int index) {
    if (sum > target) {
        return;
    }
    if (sum == target) {
        ans.add(new ArrayList<>(list));
        return;
    }
    for (int i = index; i < candidates.length; i++) {
        list.add(candidates[i]);
        sum += candidates[i];
        dfs(candidates, target, i);
        sum -= candidates[i];
        list.remove(list.size() - 1);
    }
}

Kotlin

private val ans = ArrayList<List<Int>>()
private val list = ArrayList<Int>()
private var sum = 0

fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
    dfs(candidates, target, 0)
    return ans
}

private fun dfs(candidates: IntArray, target: Int, index: Int) {
    if (sum > target) {
        return
    }
    if (sum == target) {
        ans.add(ArrayList(list))
        return
    }
    for (i in index until candidates.size) {
        list.add(candidates[i])
        sum += candidates[i]
        dfs(candidates, target, i)
        list.removeLast()
        sum -= candidates[i]
    }
}