Simple iteration (no recursion, no twiddling) + explanation


  • 20
    T

    My idea was to start out with an empty subset and either take or don't take the next element in the input array. Here's how it goes down for input [1,2,3]:

    start with

    [] // empty set is always a subset
    

    then either take or not take the next element (1), this doubles the result size:

    []   // not take 1
    [1] //      take 1 + new
    

    then take or not take the next element: 2

    []    // not take 1, not take 2
    [2]   // not take 1,     take 2 + new
    [1]   //     take 1, not take 2
    [1,2] //     take 1,     take 2 + new
    

    and finally take or not take 3.

    []      // not take 1, not take 2, not take 3
    [3]     // not take 1, not take 2,     take 3 + new
    [2]     // not take 1,     take 2, not take 3
    [2,3]   // not take 1,     take 2,     take 3 + new
    [1]     //     take 1, not take 2, not take 3
    [1,3]   //     take 1, not take 2,     take 3 + new
    [1,2]   //     take 1,     take 2, not take 3
    [1,2,3] //     take 1,     take 2,     take 3 + new
    

    And we're done, we have all 2^3 = 8 subsets generated.

    It is possible to generate these with a simple loop, there's only one trick here, the variable size. It's usually a good practice to cache method call results, but now it is cached for a different reason: because it changes in every iteration. If we don't want to end up with an infinite loop, we have to remember how many results were available in the previous iteration, which is exactly the size() of the result at the beginning of the current iteration.

    public List<List<Integer>> subsets(int[] nums) {
        Arrays.sort(nums); // make sure subsets are ordered
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>()); // start with empty set
        for (int i = 0; i < nums.length; ++i) {
            for (int j = 0, size = result.size(); j < size; ++j) { // remember
                List<Integer> subset = new ArrayList<>(result.get(j)); // copy a new one
                subset.add(nums[i]); // expand
                result.add(subset); // collect
            }
        }
        return result;
    }
    

    It is also necessary to order the input to satisfy the requirement:

    • Elements in a subset must be in non-descending order.

    Because i is increasing it means that whatever we take from nums will also be in increasing order.

    The other requirement:

    • The solution set must not contain duplicate subsets.

    is automatically guaranteed by the input specification and the algorithm walking indices straight and once:

    Given a set of distinct integers, nums, return all possible subsets. [emphasis mine]


  • 0
    Y

    I just change your this line code

    for (int j = 0, size=result.size() ; j < size ; ++j) 
    

    to

    for (int j = 0 ; j < result.size() ; j++)
    

    The compiler said time limit exceeded. I just wander does it indeed have so much differences? Because your code only take 2ms beyond 60%.

    Thanks.


  • 0
    T

    result.size() changes inside that loop, that's why we need to "remember" it (see comment). Essentially result is the source and target of that inner loop, so we only need to process the part of it that was available at the beginning of each outer loop iteration.

    To crossreference the example see the lines that have "+ new" after them, those are the ones that are generated from at "collect" in code, so the result is partitioned into [old values, new values] at the end of the inner loop and both partitions have equal length (size).

    A similar description is there in the paragraph just above the code.


  • 0
    Y

    Oh. thanks. I miss that. Thanks! u r genius!


  • 0
    Y

    what is space complexity?


Log in to reply
 

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