You could solve this problem using regular old recursion, where you make a function called subsets(nums), and then find a recursion for it. But this is slow because the Data Structure input nums changes, and there's no way to apply Backtracking to that to fix the problem. The function generates solutions all at once, so there's nothing to "undo" when you try applying Backtracking by making the array global.

The regular old recursion solution is inefficient, so we'll solve this problem by generating solutions one at a time instead. That way, we'll be able to optimize using Backtracking.

We can get all the subsets by starting with an empty array [], and then considering adding every possible element to it.

Let's find the solutions for nums = [1,2,3].

We're allowed to either add the first element or not add it, like this:

We can then consider adding and not adding the second element:

We can then consider adding and not adding the third element:

Now we've considered adding all of the elements. We now have the solution, which is all the subsets at the very end - [], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3].

Tying everything together, what we're really doing is building this tree:

We can really just solve this problem by traversing this tree.

We'll write a function visitAll that traverses the tree. When it gets to the bottom of the tree it should add the subset that it's on to the solutions. When the function is called, it needs to know the location in the tree that it's standing at. You can know where in the tree you're standing if you know the current subset subset. You also need to know the index of the element that you should add next idx.

1. Recursion

The function is called on a particular subset subset and index idx. The function should consider adding the current number it's on nums[idx] to the subset, and also not adding it. It should then continue traversing on the next number. Here's the recursion for this:

2. Base case

When the function gets to the bottom of the tree, it should add the current subset to the solution and stop. This happens when idx == len(nums).

3. Code

Combining the recursion and base case, we can easily get the solution.

Here's the recursive code:

This code is very inefficient though. This is because we're using $\small \texttt{subset + [nums[idx]]}$ which creates a whole new array, wasting time and space. This is where Backtracking comes in. Backtracking is where we make the inputs to the function like subset a global variable so we never create a new array. We also decided to make idx global to go full force with Backtracking, although this doesn't change the time or space complexity since it's just a number.

Here's the full code using Backtracking:

Time Complexity $O(n\cdot 2^n )$ . We need to build all $2^n$ possibilities, and each has up to $\texttt{n}$ entries in it.

Space Complexity $O(n\cdot 2^n )$ for the output array. The Call Stack and global parameters also take up some space, but the output array's space complexity beats them by far.

Call Stack Complexity $O(n)$. The Call Stack gets $n$ calls deep, and each call uses $O(1)$ space.