穷举vs暴搜vs深搜vs回溯vs剪枝 算法专题

一. 全排列

全排列

class Solution {List<List<Integer>> ret;List<Integer> path;boolean[] check;public List<List<Integer>> permute(int[] nums) {ret = new ArrayList<>();//存放结果path = new ArrayList<>();存放每个路径的pathcheck = new boolean[nums.length];//记录是否被使用, 对应是下标dfs(nums);return ret;}public void dfs(int[] nums){if(path.size() == nums.length){//全部遍历完ret.add(new ArrayList<>(path));//添加结果return;}for(int i = 0; i < nums.length; i++){if(!check[i]){path.add(nums[i]);check[i] = true;dfs(nums);//还原现场check[i] = false;path.remove(path.size() - 1);}}}
}

二. 子集

子集
先画决策树, 再设计代码
解法一:

class Solution {List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> subsets(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();dfs(nums, 0);return ret;}public void dfs(int[] nums, int i){//要选择的下标if(i == nums.length){ret.add(new ArrayList<>(path));return ;}//选path.add(nums[i]);dfs(nums, i + 1);//恢复现场path.remove(path.size() - 1);//不选dfs(nums, i + 1);}
}

解法二: 按照数量添加

class Solution {List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> subsets(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();dfs(nums, 0);return ret;}public void dfs(int[] nums, int pos) {ret.add(new ArrayList<>(path));//每个节点全部加入for(int i = pos; i < nums.length; i++){path.add(nums[i]);dfs(nums, i + 1);//只能添加此时下标后面的, 防止重复path.remove(path.size() - 1);//恢复现场}}
}