接上文： backtracking及其应用

Subsets

链接：https://leetcode.com/problems/subsets/
如果没有接触过backtracking，这道题的常规解法应该是位操作

func subsets(nums []int) [][]int {lth := len(nums)cnt := int(math.Pow(float64(2), float64(lth)))bits := getBits(cnt, lth)var res [][]intfor i := 0; i < cnt; i++ {var tmp []intfor j := 0; j < lth; j++ {if bits[i][j] == 1 {tmp = append(tmp, nums[j])}}res = append(res, tmp)}return res
}func getBits(cnt int, lth int) [][]int {res := make([][]int, 0, cnt)for i := 0; i < cnt; i++ {j := itmp := make([]int, lth)for k := lth-1; k >= 0; k-- {power := int(math.Pow(float64(2), float64(k)))tmp[k] = j / powerj -= power * tmp[k]}res = append(res, tmp)}return res
}

对位操作熟悉的，可以优化下上面的代码

func subsets(nums []int) [][]int {lth := len(nums)cnt := 1 << lthres := make([][]int, cnt)for i := 0; i < cnt; i++ {var tmp []intfor j := 0; j < lth; j++ {if i >> j & 1 > 0 {tmp = append(tmp, nums[j])}res[i] = tmp}}return res
}

最后给下backtracking的解法

func subsets(nums []int) [][]int {var res [][]intvar tmpList []intres = backtrack(res, tmpList, nums, 0)return res
}func backtrack(res [][]int, tmpList []int, nums []int, start int) [][]int {res = append(res, construct(tmpList))for i := start; i < len(nums); i++ {tmpList = append(tmpList, nums[i])res = backtrack(res, tmpList, nums, i+1)tmpList = tmpList[0:len(tmpList)-1]}return res
}func construct(list []int) []int {res := make([]int, len(list))for i := 0; i < len(list); i++ {res[i] = list[i]}return res
}

Subsets II

链接：https://leetcode.com/problems/subsets-ii/
基于Subsets的backtracking解法 ，这道题就简单多了
【仅贴下不同的地方】