代碼解答

func subsets(nums []int) [][]int {

    var res [][]int

    var temp []int

    //開始回溯 用指針是因?yàn)間olang slice和其他語(yǔ)言數(shù)組有些不一樣，增加長(zhǎng)度時(shí)會(huì)指向新的地址

    dfs(&res,temp,nums,0)

    return res

}

//深度優(yōu)先

func dfs(res *[][]int,temp []int,nums []int,j int){

    tp:=make([]int,len(temp),len(temp))

    //復(fù)制臨時(shí)數(shù)組記錄遍歷節(jié)點(diǎn)，避免數(shù)據(jù)混亂

    copy(tp,temp)

    *res=append(*res,tp)

    for i:=j;i<len(nums);i++{

        //遍歷到當(dāng)前節(jié)點(diǎn)

        temp=append(temp,nums[i])

        dfs(res,temp,nums,i+1)

        //回到當(dāng)前節(jié)點(diǎn)的上一節(jié)點(diǎn)

        temp=temp[:len(temp)-1]

    }

}

思路解析

讀題分析應(yīng)該用遞歸，第一個(gè)數(shù)與剩余數(shù)組合，第二個(gè)數(shù)與排除第一個(gè)數(shù)后剩余數(shù)組合...到達(dá)邊界后返回上一節(jié)點(diǎn)繼續(xù)遍歷

以輸入nums = [1,2,3]為例轉(zhuǎn)換為的樹

image

以輸入nums = [1,2,3]為例遍歷到的順序

&[[]]

&[[] [1]]

&[[] [1] [1 2]]

&[[] [1] [1 2] [1 2 3]]

&[[] [1] [1 2] [1 2 3] [1 3]]

&[[] [1] [1 2] [1 2 3] [1 3] [2]]

&[[] [1] [1 2] [1 2 3] [1 3] [2] [2 3]]

&[[] [1] [1 2] [1 2 3] [1 3] [2] [2 3] [3]]