78. Subsets
https://leetcode.com/problems/subsets/
Medium
Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0] Output: [[],[0]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10- All the numbers of
numsare unique.
Problem
Given a numeric array, return all possible combinations of its elements.
Approach
Think of each element as either “take” or “skip.” If taken, push the element into a stack; if skipped, move on. Recursively call the method until all results are enumerated.
- Declare a result variable, a stack, and a length variable for nums.
- Start recursively calling the method, passing in the recursion depth counter. In each call, first skip the value (don’t take), then push the value onto the stack, call the method again, and pop the value after the call returns.
- When the length equals the recursion depth counter (i), it means we’ve found one result — push it into the answer array. Continue until all recursive calls are completed.
Source Code
var stack []int
var ans [][]int
var length int
func subsets(nums []int) [][]int {
length = len(nums)
stack = []int{}
ans = [][]int{}
recursive(0, nums)
return ans
}
func recursive(i int, nums []int) {
if length == i {
temp := make([]int, len(stack))
copy(temp, stack)
ans = append(ans, temp)
return
}
recursive(i + 1, nums)
stack = append(stack, nums[i])
recursive(i + 1, nums)
stack = stack[:len(stack) - 1]
}
Closing
Do you have a better or simpler solution?
Feel free to leave a comment on my blog. Your feedback motivates me to keep writing. Thank you for reading, and let’s grow together to become better versions of ourselves.
