> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/02-12-2022-71.md).

# 02/12/2022 71

Method: use recursion and backtracking. The backtracking function takes three parameters: int n, int k, and int startIndex: the base condition is when the path list's size is == k, add the path list into the result list, then return. Otherwise, iterate from int i = 1 to n, add the current element to the path list.  Call the backtracking function with n, k, i + 1. Finally remove the last elements in the path list.

Time O(k \* c(n,k))

Space O(n + k)

O(c(n,k)) if counts the output. 

n! / k! (n-k)!

```
class Solution { 
    List<List<Integer>> result = new ArrayList<>(); 
    LinkedList path = new LinkedList<>(); 
    int startIndex;
    
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;     
    }

    private void backtracking(int n, int k, int startIndex){
        //base condition
        if(path.size() == k){
            result.add(new ArrayList(path));
            return;
        }
        
        //to truning unnecessary conditions
        for(int i = startIndex; i <= n - (k - path.size()) + 1; i++){
            path.add(i);
            backtracking(n, k, i + 1);
            path.removeLast();//LinkedList method  
        }
}
```

}