Backtracking - 78. Subsets

78. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

思想：

求出一个组数的子集，这算是回溯当中的最基本的入门题目，感觉地位相当于dp当中的斐波那契。这里使用dfs求解，然后不断往回回溯求解。

代码：

go：

func subsets(nums []int) [][]int {
    var res [][]int
    backtrack(nums, 0, []int{}, &res)
    return res
}

func backtrack(nums []int, start int, temp []int, res *[][]int) {
    *res = append(*res, append([]int{}, temp...))
    for i := start; i < len(nums); i++ {
        temp = append(temp, nums[i])
        backtrack(nums, i + 1, temp, res);
        temp = temp[:len(temp)-1]
    }
}