Very simple and fast java solution with explanation


  • 13
    H
    public List<List<Integer>> subsets(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> each = new ArrayList<>();
        helper(res, each, 0, nums);
        return res;
    }
    public void helper(List<List<Integer>> res, List<Integer> each, int pos, int[] n) {
        if (pos <= n.length) {
            res.add(each);
        }
        for (int i = pos; i < n.length; i++) {
            each.add(n[i]);
            helper(res, new ArrayList<>(each), i + 1, n);
            each.remove(each.size() - 1);
        }
        return;
    }
    

    The idea is use pos to keep track of the index of the array. Compare to other backracking problem like combinations, the condition that each single List adds to the List<List<Integer>> is when the index of the array is valid. Meanwhile, after adding to the List<List<Integer>> , keeping going for the for loop.


    the following is the combinations I wrote, which is very similar to this problem.

        public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> each = new ArrayList<>();
        helper(res, each, 1, n, k);
        return res;
    }
    public void helper(List<List<Integer>> res, List<Integer> each, int pos, int n, int k) {
        if (each.size() == k) {
            res.add(each);
            return;
        }
        for (int i = pos; i <= n; i++) {
            each.add(i);
            helper(res, new ArrayList<>(each), i + 1, n, k);
            each.remove(each.size() - 1);
        }
        return;
    }

Log in to reply
 

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