Fast Iterative Java Solution (1ms)


  • 0
    S

    The trick to making this Java solution fast is to use an array to keep track of which value in nums goes in each slot of the set starting at the right of the array. 0 values in the array mean it's absent, but we keep track of how far the minimum left value that we've set in the array is with the variable mini so we don't iterate over 0s.

    public class Solution {
        public List<List<Integer>> subsets(final int[] nums) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            result.add(new ArrayList<Integer>());
            final int n = nums.length;
            if (n==0) return result;
            int t[] = new int[n];
            int mini=n-1;
            for(int i = n-1; i >= 0 ; i-- ) {
                if (mini>i) { 
                    mini=i;
                }
                while (t[i] < i+1 ) {
                    t[i]++;
                    int start=t[i]+1;
                    for(int j=i+1;j<n;j++) { 
                        t[j]=start++;
                    }
                    List<Integer> a = new ArrayList<Integer>();
                    for(int j=mini;j<t.length;j++) {
                            a.add(nums[t[j]-1]);
                    }
                    result.add(a);
                    i=n-1;
                }
            }
            return result;
        }
    }
    

Log in to reply
 

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