6ms Java Recursion + Stack


  • 1
    C

    public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();

        aux(result, n, 1, k, new Stack<Integer>());
        
        return result;
        
    }
    
    private void aux(List<List<Integer>> result, int n, int currentIndex, int currentK, Stack<Integer> numbers){
        if(currentK == 0){
             result.add(new ArrayList<Integer>(numbers));
             return;
        }
        
        for(int i = currentIndex; i <= n-currentK+1; i++){
            numbers.push(i);
            aux(result, n, i+1, currentK-1, numbers);
            numbers.pop();
        }
    }

  • 0

    @cpalomino I tried to directly add numbers to result, and the result is a list of empty lists. Why is it necessary to have a new list identical to numbers?


  • 0
    C

    The numbers stack (or in your case a list I suppose) keeps changing for each recursive call and backtracks its state when the root call of aux in combine method finishes (it backtracks because of the pop). So at the end of the recursion you need to make a copy of the current state, otherwise you will be getting empty lists.

    Actually I realized doing it with a structure , such as stack, is inefficient in this case and a regular int array can be used instead. It can be initialized with size k since we know the result will always have size k.


Log in to reply
 

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