_78. Subsets.md

78. Subsets

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 02, 2024

Last updated : July 01, 2024

---

Related Topics : Array, Backtracking, Bit Manipulation

Acceptance Rate : 79.81 %

---

Solutions

• m78 Minimized Extra Space.py
• m78.py

Python

m78 Minimized Extra Space.py

# Minimizes the number of array copies formed to consistently hit 97% space efficiency
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        output = []
        def helper(currentList: List[int], remaining: List[int], add):
            if add :
                output.append(currentList.copy())
            
            if len(remaining) == 0 :
                return

            nextTerm = remaining.pop()
            helper(currentList, remaining, False)
            currentList.append(nextTerm)
            helper(currentList, remaining, True)
            remaining.append(currentList.pop())
            

        helper([], nums, True)

        return output

m78.py

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        output = []
        def helper(currentList: List[int], remaining: List[int], add):
            if add :
                output.append(currentList)
            
            if len(remaining) == 0 :
                return

            nextTerm = remaining.pop()
            remainingCopy1 = remaining.copy()
            remainingCopy2 = remaining.copy()

            helper(currentList, remainingCopy1, False)
            newCurrentList = currentList.copy()
            newCurrentList.append(nextTerm)
            helper(newCurrentList, remainingCopy2, True)

        helper([], nums, True)

        return output