Simple Java Solution with For-Each loops


  • 46
    W

    No messy indexing. Avoid the ConcurrentModificationException by using a temp list.

    public class Solution {
        public List<List<Integer>> subsets(int[] S) {
            List<List<Integer>> res = new ArrayList<>();
            res.add(new ArrayList<Integer>());
            
            Arrays.sort(S);
            for(int i : S) {
                List<List<Integer>> tmp = new ArrayList<>();
                for(List<Integer> sub : res) {
                    List<Integer> a = new ArrayList<>(sub);
                    a.add(i);
                    tmp.add(a);
                }
                res.addAll(tmp);
            }
            return res;
        }
    }

  • 67
    Y
        The idea is:
    起始subset集为:[]
    添加S0后为:[], [S0]
    添加S1后为:[], [S0], [S1], [S0, S1]
    添加S2后为:[], [S0], [S1], [S0, S1], [S2], [S0, S2], [S1, S2], [S0, S1, S2]
    红色subset为每次新增的。显然规律为添加Si后,新增的subset为克隆现有的所有subset,并在它们后面都加上Si。
    

    reference: http://bangbingsyb.blogspot.com/2014/11/leetcode-subsets-i-ii.html

    // the method below is adding elements and constructing subsets
    public List<List<Integer>> subsets2(int[] nums) {
    	List<List<Integer>> result = new ArrayList<List<Integer>>();
    	List<Integer> tmp = new ArrayList<Integer>();
    	result.add(tmp); // add empty set
    	Arrays.sort(nums);
    	for (int i=0; i<nums.length; i++){
    		int n =  result.size();
    		for(int j=0; j<n; j++){
    			// NOTE: must create a new tmp object, and add element to it.
    			tmp = new ArrayList<Integer>(result.get(j));
    			tmp.add(nums[i]);
    			result.add(new ArrayList<Integer>(tmp));
    		}   		
    	}
    	return result;
    }

  • 0
    S

    What's the complexity of this method?


  • 2
    W

    Intuitively, we are still generating all 2^n possible subsets (where n = |S| ) so the complexity will be at least 2^n.

    As for the code, initially in the outer for loop iterating over S, "res" only contains 1 subset, the empty set, []. We iterate over it in the inner loop and add a new subset, the subset containing the first element, [s0] (without loss of generality).

    In the next iteration of the outer loop, there are now 2 subsets in "res": [] and [s0]. We iterate over both of these, appending the 2nd element of S to each and add two additional subsets, [s1] and [s0, s1]. Thus res now has 4 subsets, [], [s0], [s1], [s0, s1].

    You can now see that for each iteration of the outer loop, the number of subsets we iterate over in the inner loop doubles, giving us the exponential complexity.


  • 0
    S

    Got it. Thanks!


  • 5
    Z

    Nice, you are using additional tmp list to avoid indexed accessing.

    How about this code?

     public List<List<Integer>> subsets_arraylist_clone(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        if(nums == null || nums.length ==0)
            return ret;
            
        Arrays.sort(nums);
        //init.  add empty set
        ret.add(new ArrayList<>());
        
        for(int n: nums){
            int tmpsize = ret.size();
            for(int i = 0; i < tmpsize; i ++){
                List<Integer> clone = new ArrayList<>(ret.get(i));
                clone.add(n);
                ret.add(clone);
            }
        }
        
        return ret;
    }

  • 0
    F

    why do you use a tmp ArrayList? Why not just add 'a' to result?


  • 0
    Y

    Do you know why must create a new tmp object?


  • 0
    K

    you can have try if not create a new tmp object, i think the result will be different


  • 0
    B

    If you don't create a new object and directly add element in res.get(j), you will also change the value which has been set into res, since they are using the same reference.


  • 0
    B

    Thank you for your explanation.


  • 0
    S

    Can you guys tell me how this code ensures no duplicate subsets are generated ?


  • 1
    S

    The code works out fine without sorting the array. Is there any specific reason why you sort the input array first?


  • 4
    X

    I think sort is not needed too.


  • 1

    nice solution, you can skip the temp list by just capturing the size at the start of each iteration. Here it is in C#. Also as far as I can tell the sort is not necessary (is there is reason I missed?). Thanks.

        public IList<IList<int>> Subsets(int[] nums)
        {
            IList<IList<int>> lists = new List<IList<int>>();
            lists.Add(new List<int>());
    
            for (int i = 0; i < nums.Length; i++)
            {
                int currLen = lists.Count;
                for (int j = 0; j < currLen; j++)
                {
                    IList<int> clone = new List<int>(lists[j]);
                    clone.Add(nums[i]);
                    lists.Add(clone);
                }
            }
    
            return lists;
        }
    

  • 0
    A

    @ZZJJ said in Simple Java Solution with For-Each loops:

    Nice, you are using additional tmp list to avoid indexed accessing.
    How about this code?
    public List<List<Integer>> subsets_arraylist_clone(int[] nums) {
    List<List<Integer>> ret = new ArrayList<>();
    if(nums == null || nums.length ==0)
    return ret;

    Arrays.sort(nums);
    //init.  add empty set
    ret.add(new ArrayList<>());
    
    for(int n: nums){
        int tmpsize = ret.size();
        for(int i = 0; i < tmpsize; i ++){
            List<Integer> clone = new ArrayList<>(ret.get(i));
            clone.add(n);
            ret.add(clone);
        }
    }
    
    return ret;
    

    }

    this takes O(i) every time within the loop (get a specific element from a list). I think working with a temp list is better. Or using an iterator or something like that. :-)

    I do also agree, that sorting the array is not necessary.


  • 1
    P

    Same as your implementation, just avoid creating new tmp in for loop and use CopyOnWriteArrayList instead.
    Also no need to sort.
    Please let me know if there is any issue with this approach.

    public List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>> res = new CopyOnWriteArrayList<>();
        res.add(new ArrayList<Integer>());
        
        for(int i : nums) {
            for(List<Integer> sub : res) {
                List<Integer> a = new ArrayList<>(sub);
                a.add(i);
                res.add(a);
            }
        }
        return res;
    }

  • 0
    T

    C++ implementation (3 ms, beating 96% of C++ submissions)

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            vector<vector<int>> ret = vector<vector<int>>{{}}; 
            for (int i : nums) {
                
                vector<vector<int>> temp = vector<vector<int>>(); 
                for (auto &v : ret) {
                    vector<int> extended = v; 
                    extended.push_back(i);
                    temp.push_back(extended);
                }
                // add temp to the end of ret
                ret.insert(ret.end(), temp.begin(), temp.end());
        
            }
            return ret;
        }
    };
    

Log in to reply
 

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