## DEV Community

Posted on • Originally published at alkeshghorpade.me

# LeetCode - Subsets

### Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/subsets

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 nums are unique.
``````

### Explanation

#### Backtracking

The general strategy in backtracking is either to include the current element or exclude it. We follow similar approach here. When running the recursive call we either include the current element or we exclude it.

Let's check the algorithm.

``````// main function
- initialize subset vector: vector<int> subset
- initialize result vector: vector<vector<int>> result

- call subsetsUtil(nums, result, subset, 0)

- return result

// subsetsUtil function
- res.push_back(subset)

- loop for i = index; i < nums.size(); i++
- subset.push_back(nums[i])

- subsetsUtil(nums, result, subset, i + 1)

- subset.pop_back()

- return
``````

#### C++ solution

``````class Solution {
public:
void subsetsUtil(vector<int>& nums, vector<vector<int>>& result, vector<int>& subset, int index) {
result.push_back(subset);

for(int i = index; i < nums.size(); i++){
subset.push_back(nums[i]);

subsetsUtil(nums, result, subset, i + 1);

subset.pop_back();
}

return;
}

public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> subset;
vector<vector<int>> result;

subsetsUtil(nums, result, subset, 0);

return result;
}
};
``````

#### Golang solution

``````func subsets(nums []int) [][]int {
result := make([][]int, 0)

subsetsUtils(nums, &result, []int{}, 0)

return result
}

func subsetsUtils(nums []int, result *[][]int, subset []int, index int) {
*result = append(*result, append([]int{}, subset...))

for i := index; i < len(nums); i++ {
subset = append(subset, nums[i])

subsetsUtils(nums, result, subset, i + 1)

subset = subset[:len(subset)-1]
}
}
``````

#### Javascript solution

``````var subsets = function(nums) {
function findSubset(array, subset) {
result.push([...subset]);

for(let i = 0; i < array.length; i++) {
subset.push(array[i]);

findSubset(array.slice(i + 1), subset);

subset.pop();
}
}

let result = [];
findSubset(nums, []);
return result;
};
``````

Let's dry-run our algorithm to see how the solution works.

``````Input: nums = [1, 2, 3]

Step 1: vector<int> subset
vector<vector<int>> result

Step 2: subsetsUtil(nums, res, subset, 0)

// in subsetsUtils function
Step 3: result.push_back(subset)
result.push_back([])

result = [[]]

loop for i = index, i < nums.size()
i = 0
0 < 3
true

subset.push_back(nums[i])
subset.push_back(nums[0])
subset.push_back(1)

subset = [1]

subsetsUtil(nums, res, subset, i + 1)
subsetsUtil([1, 2, 3], [[]], [1], 0 + 1)
subsetsUtil([1, 2, 3], [[]], [1], 1)

Step 4: result.push_back(subset)
result.push_back([1])

result = [[], [1]]

loop for i = index, i < nums.size()
i = 1
1 < 3
true

subset.push_back(nums[i])
subset.push_back(nums[1])
subset.push_back(2)

subset = [1, 2]

subsetsUtil(nums, res, subset, i + 1)
subsetsUtil([1, 2, 3], [[], [1]], [1, 2], 1 + 1)
subsetsUtil([1, 2, 3], [[], [1]], [1, 2], 2)

Step 5: result.push_back(subset)
result.push_back([1, 2])

result = [[], [1], [1, 2]]

loop for i = index, i < nums.size()
i = 2
2 < 3
true

subset.push_back(nums[i])
subset.push_back(nums[2])
subset.push_back(3)

subset = [1, 2, 3]

subsetsUtil(nums, res, subset, i + 1)
subsetsUtil([1, 2, 3], [[], [1], [1, 2]], [1, 2, 3], 2 + 1)
subsetsUtil([1, 2, 3], [[], [1], [1, 2]], [1, 2, 3], 3)

Step 6: result.push_back(subset)
result.push_back([1, 2, 3])

result = [[], [1], [1, 2], [1, 2, 3]]

loop for i = index, i < nums.size()
i = 3
3 < 3
false

Step 7: Here we backtrack to last line of Step 5 where
i = 2
subset = [1, 2, 3]

We execute the next line
subset.pop()

subset = [1, 2]

Step 8: We backtrack to last line of Step 4 where
i = 1
subset = [1, 2]

We execute the next line
subset.pop()

subset = [1]

Step 9: For loop continues where we execute
loop for i = index, i < nums.size()
i = 2
i < nums.size()
2 < 3
true

subset.push_back(nums[i])
subset.push_back(nums[2])
subset.push_back(3)

subset = [1, 3]

subsetsUtil(nums, res, subset, i + 1)
subsetsUtil([1, 2, 3], [[], [1], [1, 2], [1, 2, 3]], [1, 3], 2 + 1)
subsetsUtil([1, 2, 3], [[], [1], [1, 2], [1, 2, 3]], [1, 3], 3)

Step 10: result.push_back(subset)
result.push_back([1, 3])

result = [[], [1], [1, 2], [1, 2, 3], [1, 3]]

loop for i = index, i < nums.size()
i = 3
3 < 3
false

Step 11: Here we backtrack to last line of Step 3 where
i = 0
subset = [1]

We execute the next line
subset.pop()

subset = []

Step 12: For loop continues where we execute
loop for i = index, i < nums.size()
i = 1
i < nums.size()
1 < 3
true

subset.push_back(nums[i])
subset.push_back(nums[1])
subset.push_back(2)

subset = [2]

subsetsUtil(nums, res, subset, i + 1)
subsetsUtil([1, 2, 3], [[], [1], [1, 2], [1, 2, 3], [1, 3]], [2], 1 + 1)
subsetsUtil([1, 2, 3], [[], [1], [1, 2], [1, 2, 3], [1, 3]], [2], 2)

Step 13: result.push_back(subset)
result.push_back([2])

result = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2]]

loop for i = index, i < nums.size()
i = 2
2 < 3
true

subset.push_back(nums[i])
subset.push_back(nums[2])
subset.push_back(3)

subset = [2, 3]

subsetsUtil(nums, res, subset, i + 1)
subsetsUtil([1, 2, 3], [[], [1], [1, 2], [1, 2, 3], [1, 3], [2]], [2, 3], 2 + 1)
subsetsUtil([1, 2, 3], [[], [1], [1, 2], [1, 2, 3], [1, 3], [2]], [2, 3], 3)

Step 14: result.push_back(subset)
result.push_back([2, 3])

result = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]]

loop for i = index, i < nums.size()
i = 3
3 < 3
false

Step 15: Here we backtrack to last line of Step 13 where
i = 2
subset = [2, 3]

We execute the next line
subset.pop()

subset = [2]

Step 16: Here we backtrack to last line of Step 12 where
i = 1
subset = [2]

We execute the next line
subset.pop()

subset = []

Step 17: For loop continues where we execute
loop for i = index, i < nums.size()
i = 2
i < nums.size()
2 < 3
true

subset.push_back(nums[i])
subset.push_back(nums[2])
subset.push_back(3)

subset = [3]

subsetsUtil(nums, res, subset, i + 1)
subsetsUtil([1, 2, 3], [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]], [3], 2 + 1)
subsetsUtil([1, 2, 3], [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]], [3], 3)

Step 18: result.push_back(subset)
result.push_back([3])

result = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

loop for i = index, i < nums.size()
i = 3
3 < 3
false

Step 19: We have no more stack entries left. We return to main function.

Step 20: return result

So the result we return is [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]].
``````