Fast clean java code with explanation! Backtracking!


  • 2
    S

    Use backtracking. When k==0, exit current backtracking, go back to previous. Within each backtracking, if we can do more backtracking, which is when i<num.length && k>0, go to next backtracking, and let k-1.
    Since no duplicated elements accept, in next backtracking, add element after current element, which is controlled by start+1.

    public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<List<Integer>> ();
        int[] num = new int[n];
        for (int i = 0; i < n; i++){
            num[i] = i + 1;
        }
        helper(result, new ArrayList<Integer>(), num, k, 0);
        return result;
    }
    private void helper(List<List<Integer>> result, ArrayList<Integer> list, int[] num, int k, int start){
        if( k == 0){
            result.add(new ArrayList<Integer>(list));
            return;
        }
        
        for (int i = start; i < num.length && k > 0; i++){
            list.add(num[i]);
            helper(result, list, num, k - 1,i + 1);
            list.remove(list.size() - 1);
        }
    }
    

    }


Log in to reply
 

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