40.组合总和2.md

40. 组合总和 II

url

题目

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

candidates 中的每个数字在每个组合中只能使用一次。

方法

code

js

let combinationSum2 = (candidates, target) => {
    let dfs = (nums, target, start, list) => {
        if (target === 0) {
            ret.push(list.slice())
            return
        }
        for (let i = start; i < nums.length; i++) {
            if (marked[i]) {
                continue
            }
            if (i !== 0 && nums[i] === nums[i - 1] && !marked[i - 1]) {
                continue
            }
            if (nums[i] <= target) {
                list.push(nums[i])
                marked[i] = true
                dfs(nums, target-nums[i], i, list)
                marked[i] = false
                list.pop()
            }
        }
    }
    let ret = []
    let marked = Array(candidates.length).fill(false)
    candidates.sort((a, b) => {return a - b})
    dfs(candidates, target, 0, [])
    return ret
}

go

func combinationSum2(candidates []int, target int) [][]int {
	var res [][]int
	if len(candidates) == 0 {
		return res
	}
	marked := make([]bool, len(candidates))
	var dfs func(nums []int, target int, start int, list[] int)
	dfs = func(nums []int, target int, start int, list []int) {
		if target == 0 {
			res = append(res, append([]int{}, list...))
			return
		}
		for i := start; i < len(nums); i++ {
			if marked[i] {
				continue
			}
			if i != 0 && nums[i] == nums[i-1] && !marked[i-1] {
				continue
			}
			if nums[i] <= target {
				list = append(list, nums[i])
				marked[i] = true
				dfs(nums, target - nums[i], i, list)
				marked[i] = false
				list = list[0:len(list) - 1]
			}
		}
	}
	sort.Ints(candidates)
	dfs(candidates, target, 0, []int{})
	return res
}

java

class Solution {
    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 (hasVisited[i])
                continue;
            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, target - candidates[i], candidates);
                hasVisited[i] = false;
                tempCombination.remove(tempCombination.size() - 1);
            }
        }
    }

}