回溯递归(例题+思路+代码)-Toy模板网

这篇具有很好参考价值的文章主要介绍了回溯递归(例题+思路+代码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

leetcode 77

回溯递归(例题+思路+代码)

思路

组合问题适合用回溯求解。

经典解法：for循环 + 内部回溯。

每次进入回溯方法时，先判断终止条件，再进行当前层的循环，循环进行下一层递归。

代码

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> tempResult = new ArrayList<Integer>();
        dfs(result, tempResult, 1, n, k);
        return result;
    }

    public void dfs(List<List<Integer>> result, List<Integer> tempResult, int start, int n, int k) {
        if(tempResult.size() == k) {
            result.add(new ArrayList<Integer>(tempResult));
            return;
        }
        for(int i = start; i <= n; i ++) {
            tempResult.add(i);
            dfs(result, tempResult, i + 1, n, k);
            tempResult.remove(tempResult.size() - 1);
        }
    }
}