当前位置：首页 > article >正文

LeetCode回溯算法的解题思路

article 2025/1/31 23:51:15

回溯法概念

回溯法：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。

应用场景

回溯算法可以搜索得到所有的方案，本质上它是一种穷举算法。

回溯法的原理

回溯算法 = dfs+剪枝

dfs:深度优先遍历，从最上层逐步往下遍历，会用到递归。
剪枝，就是去掉不符合条件的分支。

回溯算法的框架

回溯算法其实是树形问题上的深度优先遍历.
其核心就是 for 循环里面的递归，在递归调用之前「选择元素」，在递归调用之后「撤销选择元素」。

def backtrack(已添加数据的集合, 可选的元素列表):
    if 满足结束条件:
        result.add(已添加数据的集合)
        return
    

for 元素 in 可选的元素列表:
    选择元素
    backtrack(已添加数据的集合, 可选的元素列表)
    撤销选择元素

LeetCode46，全排列。

示例如下：给定一个没有重复数字的序列，返回其所有可能的全排列。

public class LeetCode46 {
	private List<List<Integer>> result = new LinkedList<>();

	/* 主函数，输入一组不重复的数字，返回它们的全排列 */
	public List<List<Integer>> permute(int[] nums) {
		// 记录「路径」
		LinkedList<Integer> track = new LinkedList<>();
		backtrack(nums, track);
		return result;
	}

	// 已添加数据的集合：记录在 track 中
	// 选择列表：nums 中不存在于 track 的那些元素
	// 结束条件：nums 中的元素全都在 track 中出现
	public void backtrack(int[] nums, LinkedList<Integer> trackList) {
		// 触发结束条件
		if (trackList.size() == nums.length) {
			result.add(new LinkedList<>(trackList));
			return;
		}

		for (int i = 0; i < nums.length; i++) {
			// 剪枝。排除不合法的选择
			if (trackList.contains(nums[i]))
				continue;
			// 做选择
			trackList.add(nums[i]);
			// 进入下一层决策树
			backtrack(nums, trackList);
			// 取消选择
			trackList.removeLast();
		}
	}

}

LeetCode78.子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
输入：nums = [0]
输出：[[],[0]]

public class LeetCode78 {

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> resultList= new ArrayList<>();
        backTrack(0, nums, resultList, new ArrayList<>());
        return resultList;

    }


    /**
     * 回溯法进行穷举
     *
     */
    public void backTrack(int i, int[] nums, List<List<Integer>> resultList, List<Integer> tmp) {
        //添加子集
        resultList.add(new ArrayList<>(tmp));
        for(int j=i;j<nums.length;j++) {
            //添加选择的元素
            tmp.add(nums[j]);
            //递归， 子集的下标从j+1开始遍历
            backTrack(j+1, nums, resultList, tmp);
            //回溯，撤消选择
            tmp.remove(tmp.size()-1);

        }

    }

}

LeetCode22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例 1：
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2：
输入：n = 1
输出：[“()”]

提示： 1 <= n <= 8

public class LeetCode22 {

    /**
     * 生成 n 个括号()
     * @param n 括号的数量
     * @return
     */
    public List<String> generateParenthesis(int n) {
        List<String> resultList = new ArrayList<>();
        if (n == 0) {
            return resultList;
        }
        //深度优先遍历
        dfs("", n, n, resultList);
        return resultList;

    }

    /**
     *
     * 深度优先遍历，每往下遍历一次，减少一个左括号，或者右括号
     *
     * @param s 当前递归得到的结果
     * @param left 剩余的左括号数量
     * @param right 剩余的右括号数量
     * @param resultList 结果集
     */
    private void dfs(String s, int left, int right, List<String> resultList) {
        //左右括号都用完了，就说明满足条件，可以加入到结果集中
        if (left == 0 && right == 0) {
            resultList.add(s);
        }
        //回溯算法=dfs+剪枝.
        //剪枝，就是去掉不符合条件的分支。
        //如果剩余的左括号数量大于剩余的右括号数量，说明是不符合条件的。比如 )))(
        if (left > right) {
            return;
        }
        //使用左括号，左括号的数量减一
        if (left > 0) {
            dfs(s+"(", left-1, right, resultList);
        }
        //使用右括号，右括号的数量减一
        if (right > 0) {
            dfs(s+")", left, right-1, resultList);
        }

    }
}