回溯核心：递归前做选择，递归后撤销
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> res=new ArrayList<>(); if(k<=0||n<k) return res; Deque<Integer> path=new ArrayDeque<>(); dfs(n,k,1,path,res); return res; } private void dfs(int n,int k,int begin, Deque<Integer> path,List<List<Integer>> res){ if(path.size()==k){ res.add(new ArrayList<>(path)); return; } for(int i=begin;i<=n;i++){ path.addLast(i); dfs(n,k,i+1,path,res); path.removeLast(); } } }给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 示例 1： 输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ] 示例 2： 输入：candidates = [2,3,5], target = 8, 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]
提示： 1 <= candidates.length <= 30 1 <= candidates[i] <= 200 candidate 中的每个元素都是独一无二的。 1 <= target <= 500
class Solution { List<List<Integer>> res =new ArrayList<>(); //要求返回List<List<Integer>>类型 建立全局变量res public List<List<Integer>> combinationSum(int[] candidates, int target) { if (candidates == null || candidates.length == 0 || target < 0) return res; List<Integer> list = new ArrayList<>(); backtrack(0,candidates, target, list); return res; } private void backtrack(int start,int[] candidates, int target, List<Integer> list) { //终止条件 if(target<0) return; if(target==0) res.add(new ArrayList<>(list)); else{ for(int i=start;i<candidates.length;i++){ //做决策 进入递归 list.add(candidates[i]); backtrack(i,candidates,target-candidates[i],list); //撤销决策 list.remove(list.size() - 1); } } } }给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
“123” “132” “213” “231” “312” “321” 给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1:
输入: n = 3, k = 3 输出: “213” 示例 2:
输入: n = 4, k = 9 输出: “2314”
题解： 1）回溯 耗时 用链表递归提高剪枝效率 2）数学规律 3）按照顺序计算排列组合数目。通过 计算剩余数字个数的阶乘数，一位一位选出第 k 个排列的数位。 solution：
1）class Solution { public String getPermutation(int n, int k) { List<String> res=new ArrayList<>(); StringBuilder solution = new StringBuilder(); boolean[] visited=new boolean[n]; backtrack(res,solution,n,k,visited); return res.get(k-1); } void backtrack(List<String> res, StringBuilder solution,int n,int k,boolean[] visited){ if( res.size() == k) return; if( solution.length() == n){ res.add(solution.toString()); return; } for(int i = 1; i <= n; i++){ if(visited[i-1]) continue; visited[i-1] = true; solution.append(i); backtrack(res,solution,n,k,visited); visited[i-1]=false; solution.deleteCharAt(solution.length() -1); } } }给定一个 没有重复 数字的序列，返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
class Solution { List<List<Integer>> res = new LinkedList<>(); public List<List<Integer>> permute(int[] nums) { LinkedList<Integer> track = new LinkedList<>(); backtrack(nums, track); return res; } void backtrack(int[] nums,LinkedList<Integer> track){ //结束条件 if(track.size()==nums.length){ res.add(new LinkedList(track)); return; } for(int n=0;n<nums.length;n++){ //不符合条件 if(track.contains(nums[n])) continue; //做决策 剪枝 进入递归 track.add(nums[n]); backtrack(nums,track); //取消选择 track.removeLast(); } } }假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：
第 i 位的数字能被 i 整除 i 能被第 i 位上的数字整除 现在给定一个整数 N，请问可以构造多少个优美的排列？
示例1:
输入: 2 输出: 2 解释:
第 1 个优美的排列是 [1, 2]: 第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除 第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除
第 2 个优美的排列是 [2, 1]: 第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除 第 2 个位置（i=2）上的数字是1，i（i=2）能被 1 整除 说明:
N 是一个正整数，并且不会超过15。
class Solution { int count =0; public int countArrangement(int N) { int[] nums=new int[N+1]; backtrack(1,N,nums); return count; } public void backtrack(int step,int N,int[]nums){ //结束条件 if(step==N+1){ count++; return; } for(int i=1;i<=N;i++){ //不符合条件 if(nums[i]==0){ nums[i]=1; //做选择 剪枝 进入递归 if(i%step==0||step%i==0){ backtrack(step+1,N,nums); } //取消选择 nums[i]=0; } } } }n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例：
输入：4 输出：[ [".Q…", // 解法 1 “…Q”, “Q…”, “…Q.”],
["…Q.", // 解法 2 “Q…”, “…Q”, “.Q…”] ] 解释: 4 皇后问题存在两个不同的解法。 提示： 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
class Solution { public: vector<vector<string>> res; vector<vector<string>> solveNQueens(int n) { vector<string> board(n, string(n, '.')); backtrack(board, 0); return res; } void backtrack(vector<string>& board, int row) { //结束条件 if(row == board.size()) { res.emplace_back(board); return; } for(int i = 0; i < board.size(); ++i) { //排除不符合条件 剪枝 if(!isValid(board, row, i)) continue; //做决策 进入递归 board[row][i] = 'Q'; backtrack(board, row + 1); //撤销选择 board[row][i] = '.'; } } bool isValid(vector<string>& board, int row, int col) { int n = board.size(); for(int i = 0; i < row; ++i) { if(board[i][col] == 'Q') return false; } for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) { if(board[i][j] == 'Q') return false; } for(int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) { if(board[i][j] == 'Q') return false; } return true; } };题解：同上题相同，返回解的个数。 观察行列规律，正斜线列行差相等，反斜线列行和相等。 每个皇后必然不在同行列。 每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。
class Solution { public int totalNQueens(int n) { Set<Integer> columns = new HashSet<Integer>(); Set<Integer> diagonals1 = new HashSet<Integer>(); Set<Integer> diagonals2 = new HashSet<Integer>(); return backtrack(n, 0, columns, diagonals1, diagonals2); } public int backtrack(int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) { if (row == n) { return 1; } else { int count = 0; for (int i = 0; i < n; i++) { if (columns.contains(i)) { continue; } int diagonal1 = row - i; if (diagonals1.contains(diagonal1)) { continue; } int diagonal2 = row + i; if (diagonals2.contains(diagonal2)) { continue; } columns.add(i); diagonals1.add(diagonal1); diagonals2.add(diagonal2); count += backtrack(n, row + 1, columns, diagonals1, diagonals2); columns.remove(i); diagonals1.remove(diagonal1); diagonals2.remove(diagonal2); } return count; } } }