Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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
linkedin
github
slack

Post Views: 8
Posted in BasicTagged #classic, #combination, subset

Post navigation

LeetCode: Increasing Subsequences
LeetCode: Set Mismatch

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.