A simple Java solution with explanation for recursion


  • 0
    L

    The basic idea is to recurse using DFS technique. The exit condition will be to stop when you have browsed through the entire array. The tricky part may be to remember what all you have traversed and removing them to create a sublist that may be inserted when you come back from the stack to its parent stack. Example: index 0->index 1 ->index 2

    At index 2, you will have added [1,2,3]. When you come back from index 2, remove the last value from the list so that another permunation may be tried or the value could be just printed as it is.

     public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> ll = new ArrayList<>();
            ll.add(Collections.emptyList());
            List<Integer> l = new ArrayList<>();
            helper(nums,0,l,ll);
            return ll;
        }
    
        private void helper(int[] nums, int start, List<Integer> l, List<List<Integer>> ll) {
            if(start==nums.length) {
                return;
            }
            
            for(int i = start;i<nums.length;i++) {
                l.add(nums[i]);            
                helper(nums,i+1,l,ll);
                ll.add(new ArrayList<Integer>(l));
                l.remove(l.size()-1);
            }        
        }
    

Log in to reply
 

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