Simple Java solution O(n.2^n)

  • 0

    Start with an empty set. Keep gathering all the sets as and when you add/remove elements. For example: Let the set be [1,2,3]
    Initially tempList= {} at index 0
    Then you add nums[0] to {}= {1}
    Add nums[1] to {1} = {1,2}
    Add nums[2] to {1,2} = {1,2,3}
    Here the index goes beyond nums.length and hence the recursive calls start returning back.
    First it removes last element of tempList= {1,2} then 2 is gets replaced with next element = {1,3}
    Then last element of {1,3} is removed= {1} and it gets replaced by {2} and so on..
    All the above subsets are added to the power set and after all the possibilities are considered, we get our result.

    public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> allSubsets = new ArrayList<>();
            backtrack(nums, 0, new ArrayList<Integer>(), allSubsets);
            return allSubsets;
        private void backtrack(int[] nums, int index, List<Integer> tempList,  List<List<Integer>> allSubsets){
            allSubsets.add(new ArrayList<>(tempList)); //add all the cases irrespective of all the elements
            for(int i=index; i< nums.length; i++){
                backtrack(nums, i+1, tempList, allSubsets);

  • 0

    What is O(n.2^n)?

  • 0

    Why do you need sorting the array?

  • 0

    @wangmengcathy i dont think we need to sort the array

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.