Difficulty in understanding the backtracking logic

Question

I was trying to write the code for all possible subsets for an array of unique elements.

e.g. Input : nums=[1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
The output can be in any order.

I see this particular code is working correctly and satisfying all test cases.

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>>solution= new ArrayList<>();
        backtrack(solution,new ArrayList<>(), nums,0);
        return solution;
    }

    private void backtrack(List<List<Integer>> sol, List<Integer>tempList, int[] nums, int start){
        sol.add(new ArrayList<>(tempList));
        for(int i=start;i<nums.length;i++){
            if(!tempList.contains(nums[i])){
                tempList.add(nums[i]);
                backtrack(sol,tempList,nums,i);   
                tempList.remove(tempList.size()-1);
            }
        }
    }

}

I get following output which is correct [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

However I am having a doubt that when templist=[1,2,3] the if clause should prevent the further function call enclosed within it. However I see that tempList.remove(tempList.size()-1); is still being called and 2 and 3 are being removed after that.
Can anyone please clarify how this is being possible as the if condition should have prevented the removal of the last elements of the tempList. ?

Answer 1

You are correct. The if-statement will not pass when tempList = {1, 2, 3}. This makes sense as the condition is: !tempList.contains(nums[i]), since in this scenario tempList and num are identical in elements, the if-statement will not pass.

So why does it look like the if-statement passes when tempList = {1, 2, 3}? We can see that after [1, 2, 3] there are seemingly unreachable states, namely: [1, 3], [1], [2, 3], [3]. This is in fact an illusion as these states were caused by the function being called by earlier cases.

This is because the recursive function branches variably. As in, some "nodes" will branch into several other nodes, while others will simply terminate. Consider the following diagram with num = [1, 2, 3] and the starting node being the empty array:

There are two primary ways to traverse this tree.

1. Breadth-first Search
2. Depth-first Search

I believe you expected your solution to traverse it in a breadth-first search manner, which would output the following:

[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

In reality, your solution traverses the tree in a depth-first search manner which explains your output of:

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

This is because it follows the tree in this order: