LeetCode: Combination Sum II

Posted on January 10, 2018July 26, 2020 by braindenny

Combination

Similar Problems:

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, 
A solution set is: 
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/combination-sum-ii
// Basic Ideas: backtracking
//
// Complexity: Time ? Space ?
import "sort"
func dfs(combination []int, target int, candidates []int, pos int, res *[][]int) {
    if (target == 0) {
        combination2 := make([]int, len(combination))
                copy(combination2, combination)
        *res = append(*res, combination2)
        return
    }
    for i:=pos; i<len(candidates) && target-candidates[i] >= 0; i++ {
        if i>pos && candidates[i] == candidates[i-1] {
            continue
        }
                combination = append(combination, candidates[i])
        dfs(combination, target-candidates[i], candidates, i+1, res)
        combination = combination[0:len(combination)-1]
    }
}

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

## https://code.dennyzhang.com/combination-sum-ii
## Basic Ideas: Sort the list with descending order
##
## Complexity: Time O(n^2), Space O(n)
class Solution:
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if len(candidates) == 0: return []
        candidates = sorted(candidates)
        length = len(candidates)
        res = []
        for i in range(length):
            if candidates[i] > target: continue
            if candidates[i] == target:
                if [target] not in res: res.append([target])
                continue
            # try to start the result with candidates[i]
            l = self.combinationSum2(candidates[i+1:], target - candidates[i])
            for element in l:
                if not [candidates[i]]+element in res:
                    res.append([candidates[i]]+element)

        return res

Post Views: 3