【回溯算法i】golang
// 组合II, 从数组中(数组中有重复元素)找到组成目标值的组合，不重复取
func CombinationFromArrayII(candidates []int, target int) [][]int {
if len(candidates) == 0 {
return [][]int {}
}
candidates = sortWithMerge(candidates)
fmt.Printf("candidates is %v\n", candidates)
var res [][]int
var path []int
var used map[int]bool
used = make(map[int]bool)
var in func(startIndex int, used map[int]bool)
in = func(startIndex int, used map[int]bool) {
if sum(path) == target {
tmp := make([]int, len(path))
copy(tmp, path)
res = append(res, tmp)
return
}
if sum(path) > target {
return
}
for i := startIndex; i < len(candidates); i++ {
// 同一树层不存在重复元素
if i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false {
continue
}
path = append(path, candidates[i])
used[i] = true
in(i+1, used)
path = path[:len(path)-1]
used[i] = false
}
}
in(0, used)
return res
}