Java - Subset definition

  • 0

    Because Subsets have a clean recursive definition, I wanted to mirror that in code.

    The idea is that Subsets(k) = all Subsets(k-1) Union all ( Subsets(k-1) Union { nums[k]} ). In plain english, it just means if we want to add a new element to all the existing subsets, we just do precisely that (without modifying any existing subset).

    This is not an optimal solution.

    public class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            // Subsets(nums[k]) = Subsets(nums[0,k-1)) +  { Subsets(nums[0,k-1)) + nums[k] }
            List<List<Integer>> sSets = new ArrayList<>();
            // add the empty set. it is a subset of all sets
            sSets.add(new ArrayList<Integer>());
            for (int i = 0; i < nums.length; i++) {
                List<List<Integer>> appendSet = new ArrayList<>();
                for (List<Integer> existing : sSets) {
                    // copy existing set
                    List<Integer> addSubset = new ArrayList<>(existing);
                    // add the new item to all previous subsets
            return sSets;

Log in to reply

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