LeetCode: Subsets

// https://code.dennyzhang.com/subsets
// Basic Ideas: backtracking
// 
//  Add current combination to the result list
//  Then: Take the current element
//        Don't take the current element
// Complexity: Time ?, Space ?
func dfs(combination []int, nums []int, pos int, res *[][]int) {
    *res = append(*res, combination)
    for i:=pos; i<len(nums); i++ {
        combination2 := make([]int, len(combination))
        copy(combination2, combination)
        combination2 = append(combination2, nums[i])
        dfs(combination2, nums, i+1, res)
    }
}

func subsets(nums []int) [][]int {
    res := [][]int{}
    dfs([]int{}, nums, 0, &res)
    return res
}

// https://code.dennyzhang.com/subsets
// Basic Ideas: Combination
//
// Complexity: Time ?, Space ?
func dfs(combination []int, nums []int, pos int, res *[][]int) {
    if pos == len(nums) {
        *res = append(*res, combination)
        return
    }
    combination2 := make([]int, len(combination))
    copy(combination2, combination)
    combination2 = append(combination2, nums[pos])
    dfs(combination2, nums, pos+1, res)
    dfs(combination, nums, pos+1, res)
}

func subsets(nums []int) [][]int {
    res := [][]int{}
    dfs([]int{}, nums, 0, &res)
    return res
}

## https://code.dennyzhang.com/subsets
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ## Idea: Bit manipulation. The combination is 2**num. 
        ##       1. Generate a seed from 0 to 2**num-1
        ##       2. Then check all binary bits of that value. 
        ##       3. If any digit it's 1, show the corresponding value
        ## Complexity: 
        ##  1 2 3
        ##  0 0 0
        ##  0 0 1
        ##  0 1 0
        ##  ...
        ret = []
        length = len(nums)
        for i in range(0, 2**length):
            item = []
            for j in range(0, length):
                if i % 2 == 1:
                    item.append(nums[length-1-j])
                i = i/2
            ret.append(item)
        return ret