78. 子集

题意：

解题思路：

思路：DFS深度优先搜索[回溯]，具体过程看图示；

图示：

PHP代码实现：

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    public $res = [];
    function subsets($nums) {
        return $this->subsets1($nums);
       /* if (!$nums) return [];
        $this->do([],$nums, 0);
        return $this->res;*/
    }
    function do($arr, $nums, $start) {
        array_push($this->res, $arr);
        for ($i = $start; $i < count($nums); $i++) {
            array_push($arr, $nums[$i]);
            $this->do($arr, $nums, $i + 1);
            array_pop($arr);
        }
    }
    //0(2^)
    function subsets1($nums) {
        if (empty($nums)) return [];
        $result = [];
        $this->helper($nums, 0, [], $result);
        return $result;
    }
    function helper($nums, $index, $current, &$result) {
        // terminator
        if ($index == count($nums)) {
            $result[] = $current;
            return;
        }
        // split and drill down
        // 不选 not pick the number in this index
        $this->helper($nums, $index+1, $current, $result);
        //选
        $current[] = $nums[$index];
        $this->helper($nums, $index+1, $current, $result);
    }
}

GO代码实现：

var res [][]int
func subsets(nums []int) [][]int {
    res = [][]int{}
    var path []int
    subsetsBacktrack(nums, path, 0);
    return res;
}
func subsetsBacktrack(nums []int, path []int, start int){
    temp := make([]int, len(path))
    copy(temp, path)
    res = append(res, temp)
    for i := start; i < len(nums); i++ {
        path = append(path, nums[i])
        subsetsBacktrack(nums, path, i+1)
        path = path[:len(path)-1]
    }
}