040. Combination Sum II 组合总和 II

Description Medium

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

说明:

Example
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]
Solution
func combinationSum2(candidates []int, target int) [][]int {
    var rest  [][]int
    maps := map[string]bool{}
    for i := 0;i < len(candidates);i ++ {
        if target - candidates[i] > 0 {
            for _,rst_ := range combinationSum2(candidates[i+1:],target-candidates[i]) {
                temp := make([]int,len(rst_)+1)
                copy(temp,rst_)
                temp[len(rst_)] = candidates[i]
                key := string(toByte(temp))
                if _,ok := maps[key];!ok {
                    rest = append(rest,temp)
                    maps[key] = true
                }
            }
        }else if target - candidates[i] == 0{
            temp := []int{candidates[i]}
            key := string(toByte(temp))
            if _,ok := maps[key];!ok {
                rest = append(rest,temp)
                maps[key] = true
            }
        }
    }
    return rest
}

func toByte(numbs []int)[]byte  {
    sort.Ints(numbs)
    bytes := make([]byte,len(numbs))
    for i,v := range numbs{
        bytes[i]=byte(v)
    }
    return bytes
}






//solution 2
func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    path := make([]int,len(candidates))
    return find(candidates,path,target,0,0)
}

func find(candidates,path []int,target,index,pathIndx int)[][]int  {
    var result [][]int
    for i := index;i < len(candidates);i ++ {
        v := candidates[i]
        if i > index && v == candidates[i-1] {
            continue
        }
        if v == target {
            found := make([]int,0,pathIndx+1)
            found = append(found,path[0:pathIndx]...)
            found = append(found,v)
            result = append(result,found)
        }else if v < target {
            path[pathIndx] = v
            found := find(candidates,path,target-v,i+1,pathIndx+1)
            result = append(result,found...)
        }else {
            break
        }
    }
    return result

}

leetCode地址