LeetCode: Subsets Posted on February 19, 2018July 26, 2020 by braindenny Subsets Similar Problems: Subsets II CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #subset, #backtracking, #dfs, #classic Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,3], a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. // 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 Post Views: 8