Given an integer array nums of unique elements, return all possible subsets (the power set). The belwo code is returning wrong answer for input [1,2].How to fix it?

Expected Output is

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

I am getting the below output

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

I have written the below code

class Solution {
    
    private List<List<Integer>> ans= new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        
        
        
        solve(nums,0,new ArrayList<>()) ;
        
        return ans;
        
    }
    
    
    public void solve(int[] nums,int i,List<Integer> output)
    {
        if(i==nums.length )
        {
            
            ans.add(new ArrayList(output));
            return;
            
        }
        
        
       // exclude the element
        solve(nums,i 1,output);
        
        
        //include the element
        output.add(nums[i]);
        solve(nums,i 1,output);
        
            
    }
}

CodePudding user response：

Not sure your approach is right. you add element to your running list output but then you don't remove it which is what an usual backtracking does. You add to the running list, recurse and then remove the last element chosen. The correct solve looks like:

    public static void solve(int[] nums,int i,List<Integer> output)
    {
        ans.add(new ArrayList<>(output));
        while (i < nums.length) {
            output.add(nums[i]);
            solve(nums, i 1, output);
            output.remove(output.size()-1);
            i  ;
        }
        
    }

You can see that I added nums[i] to the output , recurse on the remaining list and then removed the last element added.

Output for example input [1,2] with this method is:

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