[LC] 0040 Combination Sum II

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/combination-sum-ii/">Combination Sum II</a>
 * 数组；回溯
 */
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }

    public void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (target - candidates[i] < 0) {
                break;
            }
            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }
}

Go

import "sort"

func combinationSum2(candidates []int, target int) [][]int {
    res := [][]int{}
    sort.Ints(candidates)
    backtrack(candidates, target, 0, []int{}, &res)
    return res
}

func backtrack(candidates []int, target int, start int, path []int, res *[][]int) {
    if target == 0 {
        *res = append(*res, append([]int{}, path...))
        return
    }
    for i := start; i < len(candidates); i++ {
        if i > start && candidates[i] == candidates[i-1] {
            continue
        }
        if target < candidates[i] {
            break
        }
        path = append(path, candidates[i])
        backtrack(candidates, target-candidates[i], i+1, path, res)
        path = path[:len(path)-1]
    }
}

JavaScript

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
    let res = [];
    candidates.sort((a, b) => a - b);
    backtrack(candidates, target, 0, [], res);
    return res;
};

function backtrack(candidates, target, start, path, res) {
    if (target === 0) {
        res.push([...path]);
        return;
    }
    for (let i = start; i < candidates.length; i++) {
        if (i > start && candidates[i] === candidates[i - 1]) {
            continue;
        }
        if (target - candidates[i] < 0) {
            break;
        }
        path.push(candidates[i]);
        backtrack(candidates, target - candidates[i], i + 1, path, res);
        path.pop();
    }
}

PHP

class Solution {

    /**
     * @param Integer[] $candidates
     * @param Integer $target
     * @return Integer[][]
     */
    function combinationSum2(array $candidates, int $target): array {
        $res = [];
        sort($candidates);
        $this->backtrack($candidates, $target, 0, [], $res);
        return $res;
    }

    function backtrack($candidates, $target, $start, $path, &$res): void {
        if ($target === 0) {
            $res[] = $path;
            return;
        }
        for ($i = $start; $i < count($candidates); $i++) {
            if ($i > $start && $candidates[$i] === $candidates[$i - 1]) {
                continue;
            }
            if ($target - $candidates[$i] < 0) {
                break;
            }
            $path[] = $candidates[$i];
            $this->backtrack($candidates, $target - $candidates[$i], $i + 1, $path, $res);
            array_pop($path);
        }
    }
}