回溯随笔

回溯问题通用模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

组合问题

在1-n数中找到所有大小为k的组合，leetcode：77
https://leetcode.cn/problems/combinations/

解法：

class Solution 
{
    List<List<Integer>> result;
    LinkedList<Integer> path;
    public List<List<Integer>> combine(int n, int k) 
    {
        result = new ArrayList<>();
        path = new LinkedList<>();
        traceback(n,k,1);
        return result;
    }
    public void traceback(int n, int k,int startIndex)
    {
        //递归终止条件，相当于到达叶节点，path大小达到说明此时得到了一个目标组合
        if(path.size() == k)
        {
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex;i <= n;i++)
        {
            path.add(i);//做选择
            traceback(n,k,i+1);//把该选择移除出选择列表
            path.removeLast();//撤销选择
        }
    }
}

组合问题剪枝优化

可考虑的情况：做完当前选择后剩下的选择列表大小 >= 达到大小k还需选择的元素数
例子：n = 4 k = 4 此时startIndex = 2，已有列表大小path.size()为1，加入当前元素后为path.size()+1为2，剩下的选择列表大小为n - startIndex,还需的元素数为k - (path.size() + 1)
n - startIndex >= k - (path.size() + 1) 则startIndex <= n - k + path.size() + 1 (+1容易被漏掉)