Java - Subset definition


  • 0
    D

    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
                    addSubset.add(nums[i]);
                    
                    appendSet.add(addSubset);
                }
                
                sSets.addAll(appendSet);
                
            }
            
            return sSets;
        }
    }
    

Log in to reply
 

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