Leetcode: Combinations

This question is mainly asked by Facebook, Amazon, and Apple.

Here is the question:

Given 2 integers n and k, we want to return all possible combinations of k number from 1 to n. We are able to return the number in any order.

Here are the 2 examples enumerated:

Example 1:

Input: n = 4, k = 2

Output:

[

  [2,4],

  [3,4],

  [2,3],

  [1,2],

  [1,3],

  [1,4],

]

Example 2:

Input: n = 1, k = 1

Output: [[1]]

Constraints:

1 <= n <= 20

1 <= k <= n

Fortunately, I can return the answer in any order, so let's do this.

Backtracking is an algorithm for finding all solutions by exploring all the potential candidates and backtracking discards the solution if it turns out to be not a solution. If a current combination is done, we first want to add it to the output and subsequently iterate over the integers first to n, where we add an integer and proceed to add more integers and backtrack by removing i from curr. 

Here's the solution: 

class Solution {

    List<List<Integer>> output = new LinkedList());

    int n;

    int k;

    public void backtrack(int first, LinkedList<Integer> curr) {

        if(curr.size() == k) output.add(new LinkedList(curr));

        for (int i = first; i < n + 1; ++ i) {

            curr.add(i);

            backtrack(i + 1, curr);

            curr.removeLast();

        }

    }

    public List<List<Integer>> combine(int n, int k) {

        this.n = n;

        this.k = k;

        backtrack(1, new LinkedList<Integer>());

        return output;

    }    

}