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;
};

Dry Run

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]].