Java: Subsets

Thought Process

To generate all possible subsets of a given array, we use backtracking. We start by adding the current subset to the result and then recursively explore all possible combinations by including and excluding elements. This ensures that we generate all 2n subsets, where 'n' is the size of the input array. 

class Solution {

    public void backTrack(List<List<Integer>> ans, List<Integer> tmp, int[] nums, int start){

        ans.add(new ArrayList<>(tmp));

        for(int i=start;i<nums.length;i++){

            // Add an Element to the List and Taking that element try to find the solution
            tmp.add(nums[i]);
            backTrack(ans,tmp,nums,i+1);
            // Finally, remove the added Element (backTrackStep)   
            tmp.remove(tmp.size()-1);
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();

        backTrack(ans,tmp,nums,0);
        return ans;
    }
}

Code Complexity

Time Complexity: O(2n)

The algorithm generates all possible subsets of the input array, resulting in 2n subsets, where 'n' is the size of the input.

Space Complexity: O(n)

The recursion stack depth is proportional to the size of the input('n'), and the temporary list stores intermediate results.

Code copied!