算法题/排列组合：不含重复数字的组合

题目

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

示例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]]
解释：

解答

Java

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> combinations = new ArrayList<>();
    backtracking(new ArrayList<>(), combinations, 0, target, candidates);
    return combinations;
}

private void backtracking(List<Integer> tempCombination, List<List<Integer>> combinations,int start, int target, final int[] candidates) {
    if (target == 0) {
        combinations.add(new ArrayList<>(tempCombination));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] <= target) {
            tempCombination.add(candidates[i]);
            backtracking(tempCombination, combinations, i, target - candidates[i], candidates);
            tempCombination.remove(tempCombination.size() - 1);
        }
    }
}

JavaScript

function combinationSum(candidates, target) {
    const combinations = [];
    backtracking([], combinations, 0, target, candidates);
    return combinations;
}

function backtracking(tempCombination, combinations, start, target, candidates) {
    if (target === 0) {
        combinations.push([...tempCombination]);
        return;
    }
    for (let i = start; i < candidates.length; i++) {
        if (candidates[i] <= target) {
            tempCombination.push(candidates[i]);
            backtracking(tempCombination, combinations, i, target - candidates[i], candidates);
            tempCombination.pop();
        }
    }
}

Python

def combinationSum(candidates, target):
    combinations = []
    backtracking([], combinations, 0, target, candidates)
    return combinations

def backtracking(tempCombination, combinations, start, target, candidates):
    if target == 0:
        combinations.append(list(tempCombination))
        return
    for i in range(start, len(candidates)):
        if candidates[i] <= target:
            tempCombination.append(candidates[i])
            backtracking(tempCombination, combinations, i, target - candidates[i], candidates)
            tempCombination.pop()

Go

func combinationSum(candidates []int, target int) [][]int {
	combinations := [][]int{}
	backtracking([]int{}, &combinations, 0, target, candidates)
	return combinations
}

func backtracking(tempCombination []int, combinations *[][]int, start, target int, candidates []int) {
	if target == 0 {
		*combinations = append(*combinations, append([]int(nil), tempCombination...))
		return
	}
	for i := start; i < len(candidates); i++ {
		if candidates[i] <= target {
			tempCombination = append(tempCombination, candidates[i])
			backtracking(tempCombination, combinations, i, target-candidates[i], candidates)
			tempCombination = tempCombination[:len(tempCombination)-1]
		}
	}
}