回溯算法的简单使用

func subsets(nums []int) [][]int {
    // 保存最终结果
    result := make([][]int, 0)
    // 保存中间结果
    list := make([]int, 0)
    backtrack(nums, 0, list, &result)
    return result
}
// nums 给定的集合
// pos 下次添加到集合中的元素位置索引
// list 临时结果集合(每次需要复制保存)
// result 最终结果
func backtrack(nums []int, pos int, list []int, result *[][]int) {
    // 把临时结果复制出来保存到最终结果
    ans := make([]int, len(list))
    copy(ans, list)
    *result = append(*result, ans)
    // 选择、处理结果、再撤销选择
    //遍历一遍所有字母，选择则加入临时数组，再进行下一步子步骤，子步骤执行完回退
    //假设nums=[1,2,3,4,5,6]
    //第一步：加入1,list=[1]
    //第二步：递归调用，result=[[],[1]],循环开始,pos=1,加入2，list=[1,2]
    //第三步：递归调用，result=[[],[1],[1,2]]，循环开始,pos=2,list=[1,2,3]
    //...........................................
    //result=[[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5],[1,2,3,4,5,6]],循环开始，但此时pos=6，len=6,循环不执行，结束最深层递归,返回上一层pos=5减少最后一个元素，list=[1,2,3,4,5]
    //pos=5 i=6 len=6 循环结束返回上一层
    //pos=4 i=4 list=[1,2,3,4]
    //pos=4 i=5 num[5]=6,list=[1,2,3,4,6],进入子递归。。。。。
    //....................
    
    
    //pos=4 i=6 len=6循环结束返回上一层
    //pos=3 i=4 list=[1,2,3,5]
    //.....     list=[1,2,3,5,6]
//list数组直接添加当前递归结点的下一个数，即为遍历左结点
//回溯到上一个状态（根结点）需要对临时数组长度减1，并且该次递归结束（这里右节点和根节点一样，所以不用遍历）
    for i := pos; i < len(nums); i++ {
        //一直遍历到最底层左叶结点
        list = append(list, nums[i])
        //递归调用该程序
        backtrack(nums, i+1, list, result)
        //返回上一个状态并结束本次递归
        list = list[0 : len(list)-1]
    }
}