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

题目

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

示例1：

输入：candidates=[10,1,2,7,6,1,5], target=8
输出：[[1,1,6],[1,2,5],[1,7],[2,6]]
解释：

示例2：

输入：candidates=[2,5,2,1,2], target=5
输出：[[1,2,2],[5]]
解释：

解答

Java

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<List<Integer>> combinations = new ArrayList<>();
    Arrays.sort(candidates);
    backtracking(new ArrayList<>(), combinations, new boolean[candidates.length], 0, target, candidates);
    return combinations;
}


private void backtracking(List<Integer> tempCombination, List<List<Integer>> combinations, boolean[] hasVisited, 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 (i != 0 && candidates[i] == candidates[i - 1] && !hasVisited[i - 1]) {
            continue;
        }
        if (candidates[i] <= target) {
            tempCombination.add(candidates[i]);
            hasVisited[i] = true;
            backtracking(tempCombination, combinations, hasVisited, i + 1, target - candidates[i], candidates);
            hasVisited[i] = false;
            tempCombination.remove(tempCombination.size() - 1);
        }
    }
}

JavaScript

function combinationSum2(candidates, target) {
  let combinations = [];
  candidates.sort((a, b) => a - b);
  backtracking([], combinations, new Array(candidates.length).fill(false), 0, target, candidates);
  return combinations;
}

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

Python

def combinationSum2(candidates, target):
    combinations = []
    candidates.sort()
    backtracking([], combinations, [False] * len(candidates), 0, target, candidates)
    return combinations


def backtracking(tempCombination, combinations, hasVisited, start, target, candidates):
    if target == 0:
        combinations.append(list(tempCombination))
        return
    for i in range(start, len(candidates)):
        if i != 0 and candidates[i] == candidates[i - 1] and not hasVisited[i - 1]:
            continue
        if candidates[i] <= target:
            tempCombination.append(candidates[i])
            hasVisited[i] = True
            backtracking(tempCombination, combinations, hasVisited, i + 1, target - candidates[i], candidates)
            hasVisited[i] = False
            tempCombination.pop()

Go

func combinationSum2(candidates []int, target int) [][]int {
	combinations := [][]int{}
	sort.Ints(candidates)
	backtracking([]int{}, &combinations, make([]bool, len(candidates)), 0, target, candidates)
	return combinations
}

func backtracking(tempCombination []int, combinations *[][]int, hasVisited []bool, start, target int, candidates []int) {
	if target == 0 {
		comb := make([]int, len(tempCombination))
		copy(comb, tempCombination)
		*combinations = append(*combinations, comb)
		return
	}
	for i := start; i < len(candidates); i++ {
		if i != 0 && candidates[i] == candidates[i-1] && !hasVisited[i-1] {
			continue
		}
		if candidates[i] <= target {
			tempCombination = append(tempCombination, candidates[i])
			hasVisited[i] = true
			backtracking(tempCombination, combinations, hasVisited, i+1, target-candidates[i], candidates)
			hasVisited[i] = false
			tempCombination = tempCombination[:len(tempCombination)-1]
		}
	}
}