77. 组合

Problem: 77. 组合

[TOC]

思路

回溯法，这里记录几个做回溯法的优化小tips。回溯时如果使用正向遍历，需要多传一个参数n；但是如果逆向遍历，并且数组从固定的数（如1）开始，n可以一开始就当作当前位置传过去，然后在回溯时遍历到0，减少一个参数。

另一个是，分析回溯问题的时间复杂度，有一个通用公式：路径长度×搜索树的叶子数。

复杂度

• 时间复杂度: $O(k⋅C(n,k))。
• 空间复杂度: $O(k)$

Code

class Solution {
    List<List<Integer>> ans;

    public List<List<Integer>> combine(int n, int k) {
        ans = new ArrayList<>();
        List<Integer> a = new ArrayList<>();
        dfs(a, n, k);
        return ans;
    }

    public void dfs(List<Integer> now, int index, int k) {
        if (now.size() == k) {
            ans.add(new ArrayList<>(now));
            return;
        }
        for (int i = index; i >= 1; i--) {
            now.add(i);
            dfs(now, i - 1, k);
            now.remove(now.size() - 1);
        }
    }
}