[LeetCode] #77 Combinations

Time complexity: O(2^n)
because T(n) = kn + T(n-1) + T(n-2) +...+ T(2) + T(1), => O(2^n) ,  see https://discuss.leetcode.com/topic/2163/what-is-the-time-complexity-of-the-recursive-solution-for-this-problem-how-to-get-it/3

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