Divide & Conquer - Java AC Solution


  • 0
    C

    A solution using the divide & conquer methodology. Start from an empty list and index -1, for every index "idx" after this index, create a new copy of the current list and add the number at idx to the new copy, and pass on this new copy to the subproblem, which is the sub-array from idx + 1 to the end.

    I'm starting from -1 because that's the case for an empty list.

    class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> res = new LinkedList<>();
            subsets(nums, -1, new LinkedList<>(), res);
            return res;
        }
        
        void subsets(int[] nums, int startIdx, List<Integer> parent, List<List<Integer>> res) {
            List<Integer> thisList = new LinkedList<>(parent);
            if (startIdx != -1) thisList.add(nums[startIdx]);
            res.add(thisList);
            for (int i = startIdx + 1; i < nums.length; i++) {
                subsets(nums, i, thisList, res);
            }
        }
    }
    

Log in to reply
 

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