Java subsets solution


  • 32
    V

    public class Solution {

    public List<List<Integer>> subsets(int[] S) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
       
        if(S.length == 0){
            return result;
        }
        
        Arrays.sort(S);
        dfs(S, 0, new ArrayList<Integer>(), result);
        return result;
    }
    
    public void dfs(int[] s, int index, List<Integer> path, List<List<Integer>> result){
        result.add(new ArrayList<Integer>(path));
        
        for(int i = index; i < s.length; i++){
            path.add(s[i]);
            dfs(s, i+1, path, result);
            path.remove(path.size()-1);
        }
    }
    

    }


  • 0
    E

    very nice code...
    but could you tell me why "path.remove(path.size()-1)"? I am still struggling while trying to understand your code.
    Thank you!


  • 0
    Y

    Yeah! I have the same question. If you ever figured it out, please let me know! Thanks


  • 0
    A

    I have a basically same solution. But I get a TLE. Why!?


  • 0
    M

    I know the time complexity is 2 power n because that's the number of subsets how do i get there with a mathematical formula? anyone please?, i was asked this in a startup interview today! I tried with masters theorem but couldn't get there


  • 2
    K

    The reason for doing that is to reuse the same list to find the next subset.

    For example:
    If S = {1,2,3} and path is currently: {1,2,3}, after adding a copy of path into result, we want to find the next subset, which is {1,3}. So to do this, we need to remove the last two elements from path. ({2,3}). If we add "path.remove(path.size()-1);" at the end of the recursive function, we would essentially be popping off the last element every time we jump back up to the previous recursive function. Going back to the example I gave earlier, when we get back to the recursive function that has {1,2} as the path, we would pop off {2}, and as part of the for loop, we would put in the next element, which is {3}, and get the path {1,3}.


  • 0
    Y

    @kevin3 Thank you very much!


  • 0
    W

    I also got that TLE, do you why? Or anybody could tell me? Thanks


  • 0
    T

    I also have similar solutions. but why do I have TLE?


  • 0
    Z

    @emilyniuniu Guess by now you have probably got the answer. path is gorwing when recursion goes deeper and shrinking when recursion returns.

    It's a common trick to keep track of current path (or context in fancy terms). Working out path on a piece of paper may help.


  • 0
    Z

    Hi guys, could you plz tell me why I cannot just use result.add(path) instead of result.add(new ArrayList<Integer>(path));;


  • 0

    @zhang.xianl path is only reference pointing to the same object, you need to copy a new one then add to the result, otherwise you only got one path in the result


  • 0
    A

    @alanwang Can you give me more specific explaination on this reference pointer? Thanks.


  • 1
    C

    @vy7Sun no need to sort the array first


  • 0
    J

    Why do you need to sort the array?


Log in to reply
 

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