1291-顺次数

力扣1291

https://leetcode-cn.com/problems/sequential-digits/

乍一看有点怪，看似回溯又不像。其实是回溯，但是没有123 124 125这样的过程，每一次for循环还在，但是每次递归进入一次后就被剪枝了（判断12后面必须跟3）

public List<Integer> sequentialDigits(int low, int high) {
    backtrace(low, high, 0, 1);
    Collections.sort(res);
    return res;
}

private List<Integer> res = new ArrayList<>();
public void backtrace(int low, int high, int path, int index){
    //结束条件
    if (path > high) return ;
    if (path >= low && path <= high){
        res.add(path);
    }
    //选择列表实际为起始数字
    for (int i = index; i <= 9; i++) {
        //剪枝
        if (path != 0 && path % 10 + 1 != i) return;
        //选择
        path = path * 10 + i;
        //递归
        backtrace(low, high, path, i + 1);
        //撤销
        path = path / 10;
    }
}