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.

Example 1:

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

Problem Link

Subsets - LeetCode

Recursion Tree for Backtracking

Code

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        
        vector<vector<int>> res;
        vector<int> temp;
        backtrack(res,temp,nums,0);
        return res;
    }
    void backtrack(vector<vector<int>> &res,vector<int>& temp,vector<int> nums,int start)
    {
        for(int i=start;i<nums.size();i++)
        {
            temp.push_back(nums[i]);
            backtrack(res,temp,nums,i+1);
            temp.pop_back();
        }
        res.push_back(temp);
    }
};

Complexity Analysis:

• Time Complexity: O(2 ^ n).For every index i two recursive case originates, So Time Complexity is O(2^n).
• Space Complexity: O(n).The space complexity can be reduced if the output array is not stored and the static and global variable is used to store the output string.