LeetCode-77

题目

结果

代码

class Solution {
    // Save the final answer
    private final List<List<Integer>> ans = new LinkedList<>();
    // Save the nums from 1 to n
    private final List<Integer> nums = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        // Initialize the nums list
        for (int i = 0; i < n; i++) {
            nums.add(i + 1);
        }

        combine(new LinkedList<>(), k);
        return ans;
    }

    private void combine(List<Integer> tmp, int k) {
        // Stop recurse when k == 0
        if (k == 0) {
            ans.add(new LinkedList<>(tmp));
            return;
        }

        int index = tmp.size() == 0 ? 0 : tmp.get(tmp.size() - 1);
        for (int i = index; i < nums.size(); i++) {
            List<Integer> newTmp = new ArrayList<>(tmp);
            newTmp.add(nums.get(i));
            // Recursive call
            combine(newTmp, k - 1);
        }
    }
}

复杂度

时间复杂度：O（n！）

空间复杂度：O（n²）