Why my 1st solution failed?


  • 0
    D

    This is my solution 1:

    public class Solution {

    public List<List<Integer>> combine(int n, int k){
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        combine(n, k, 1, result, new ArrayList<Integer>());
        return result;
    }
    
    public void combine(int n, int k , int start, List<List<Integer>> result, ArrayList<Integer> l){
        if(k == 0){
            result.add(l);
            return;
        }
        for(int i = start; i <= n; ++i){
    
            l.add(i);
            combine(n, k - 1, i + 1, result, l);
        }
    }
    
    
    }
    

    Result: small test cases passed. But big test cases time exceed.

    Submission Result: Time Limit Exceeded Last executed input: 10, 5

    Solution 2:

    public class Solution {
    
    public List<List<Integer>> combine(int n, int k){
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        combine(n, k, 1, result, new ArrayList<Integer>());
        return result;
    }
    
    public void combine(int n, int k , int start, List<List<Integer>> result, ArrayList<Integer> l){
        if(k == 0){
            result.add(l);
            return;
        }
        for(int i = start; i <= n; ++i){
            ArrayList<Integer> a = (ArrayList<Integer>) l.clone();
            a.add(i);
            combine(n, k - 1, i + 1, result, a);
        }
    }
    
    
    }
    

    Passed all test cases.

    the main difference is clone of the list. But why? is the solution A wrong or just slow? Why using clone is faster here? Really confused.


Log in to reply
 

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