当前位置： 代码迷 >> 综合 >> 排列组合（回溯）：全排列+N皇后+递增子序列+电话号码组合+和为目标值的组合+k个数的组合
  详细解决方案

排列组合（回溯）：全排列+N皇后+递增子序列+电话号码组合+和为目标值的组合+k个数的组合

热度：11   发布时间：2023-12-23 16:41:46.0

——回溯是DFS中的一种

参考LeetCode46题解

回溯公式：

result = []
def backtrack(路径, 选择列表):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:做选择递归：backtrack(路径, 选择列表)撤销选择

具体解释，可参考知乎文章，写的很好：https://zhuanlan.zhihu.com/p/93530380

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」
决策树如下：
决策树

一、全排列

1.1 无重复数字全排列

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

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

class Solution {
    public List<List<Integer>> permute(int[] nums) {
    //输入：[1,2,3]List<List<Integer>> res = new ArrayList<>();List<Integer> list = new ArrayList<>();backtrack(res,list,nums);return res;}public void backtrack(List<List<Integer>> res,List<Integer> list,int[] nums){
    //满足结束条件时if(list.size() == nums.length){
    res.add(new ArrayList<Integer>(list));//加入到路径return;}for(int i:nums){
    //排除不合法选择if(!list.contains(i)){
    //做选择list.add(i);//进入下一行决策backtrack(res,list,nums);//撤销选择list.remove(list.size()-1);//递归结束后，将每次递归进去的数撤出}}}
}

1.2 有重复数字全排列

题目来源：LeetCode47https://leetcode-cn.com/problems/permutations-ii/

给定一个可包含重复数字的序列，返回所有不重复的全排列。
在这里插入图片描述

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();List<Integer> list = new ArrayList<>();boolean[] isUsed = new boolean[nums.length];Arrays.sort(nums);backtrack(res,list,nums,isUsed);return res;}public void backtrack(List<List<Integer>> res,List<Integer> list,int[] nums,boolean[] isUsed){
    //结束条件if(list.size() == nums.length){
    res.add(new ArrayList<Integer>(list));//加入到路径return;}int lastUsed = Integer.MIN_VALUE;for(int i=0;i<nums.length;i++){
    //排除不合法if(isUsed[i] == false && nums[i] != lastUsed){
    isUsed[i] = true;//做选择list.add(nums[i]);//下一决策树backtrack(res,list,nums,isUsed);lastUsed = nums[i];isUsed[i] = false;//撤销上一个选择list.remove(list.size()-1);}}}
}

1.3 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
在这里插入图片描述

class Solution {
    List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {
    List<Integer> list = new ArrayList<>();baktrack(list,nums,0);res.add(new ArrayList<>());//加入空的return res;}public void baktrack(List<Integer> list,int[] nums,int index){
    for(int i=index;i<nums.length;i++){
    list.add(nums[i]);res.add(new ArrayList<>(list));baktrack(list,nums,i+1);list.remove(list.size()-1);}}
}

1.4 字符串全排列

【题目】 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

参考博客：https://blog.csdn.net/Strom72/article/details/80738818
在这里插入图片描述

完整代码：

import java.util.*;public class Solution {
    public static ArrayList<String> Permutation(String str) {
    ArrayList<String> ans=new ArrayList<>();//所有排列的可能都在这里if(str!=null||str.length()>0){
    help(0,str.toCharArray(),ans);Collections.sort(ans);}return ans;}public static void help(int i,char[] cha,ArrayList<String> ans){
    if(i==cha.length-1){
    String val = String.valueOf(cha);if(!ans.contains(val)){
    ans.add(val);}}else{
    for(int j=i;j<cha.length;j++){
    swap(i,j,cha);//依次选一个数固定住help(i+1,cha,ans);//让后面的进行全排列swap(i,j,cha);//恢复原来的模样，回溯关键}}}public static void swap(int i,int j,char[] cha){
    char temp=cha[i];cha[i]=cha[j];cha[j]=temp;}public static void main(String[] args){
    Scanner sc = new Scanner(System.in);String str = sc.next();System.out.println(Permutation(str));}
}

二、N皇后问题

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击（包括斜线方向）。
在这里插入图片描述

上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
在这里插入图片描述

import java.util.*;public class Solution {
    public static void main(String[] args){
    Scanner sc = new Scanner(System.in);int n = sc.nextInt();System.out.println(solveNQueens(n));}public static List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<List<String>>();int[] queens = new int[n];Arrays.fill(queens, -1);Set<Integer> columns = new HashSet<Integer>();//同一列是否有皇后Set<Integer> diagonals1 = new HashSet<Integer>();//斜线1：左上-右下Set<Integer> diagonals2 = new HashSet<Integer>();//斜线2：右上-左下backtrack(res, queens, n, 0, columns, diagonals1, diagonals2);return res;}public static void backtrack(List<List<String>> res, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
    if (row == n) {
    List<String> board = generateBoard(queens, n);res.add(board);} else {
    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;}queens[row] = i;columns.add(i);diagonals1.add(diagonal1);diagonals2.add(diagonal2);backtrack(res, queens, n, row + 1, columns, diagonals1, diagonals2);queens[row] = -1;columns.remove(i);diagonals1.remove(diagonal1);diagonals2.remove(diagonal2);}}}public static List<String> generateBoard(int[] queens, int n) {
    List<String> board = new ArrayList<String>();for (int i = 0; i < n; i++) {
    char[] row = new char[n];Arrays.fill(row, '.');row[queens[i]] = 'Q';board.add(new String(row));}return board;}
}

在这里插入图片描述

三、递增子序列

LeetCode491：https://leetcode-cn.com/problems/increasing-subsequences/

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
在这里插入图片描述

class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();List<Integer> list = new ArrayList<>();backTrace(res,list,nums,-1);return res;}public void backTrace(List<List<Integer>> res,List<Integer> list,int[] nums,int begin){
    //判断满足条件if(list.size()>=2) {
    //加入到路径res.add(new ArrayList<>(list));}Set<Integer> set = new HashSet<>();for(int i = begin+1;i<nums.length;i++){
    //排除不合法if(!set.contains(nums[i])){
     set.add(nums[i]);//做选择：如果出现更大的数if(begin == -1 || nums[i] >= nums[begin]){
    list.add(nums[i]);//进入下一行决策backTrace(res,list,nums,i);//撤销选择list.remove(list.size()-1);}}}}
}

四、电话号码的组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
在这里插入图片描述

class Solution {
    public List<String> letterCombinations(String digits) {
    List<String> res = new ArrayList<>();int len = digits.length();if(len==0) {
    return res;}Map<Character,String> map = new HashMap<>();map.put('2',"abc");map.put('3', "def");map.put('4', "ghi");map.put('5', "jkl");map.put('6', "mno");map.put('7', "pqrs");map.put('8', "tuv");map.put('9', "wxyz");StringBuffer sb = new StringBuffer();backtrack(digits,map,res,0,sb);return res;}//回溯public void backtrack(String digits,Map<Character,String> map,List<String> res,int begin,StringBuffer sb){
    //满足条件时，加入到路径if(begin == digits.length()){
    res.add(sb.toString());return;}char c = digits.charAt(begin);String ss = map.get(c);//要从中选择字符的字符串for(int i = 0;i < ss.length();i++){
    //做选择sb.append(ss.charAt(i));//进入下一决策backtrack(digits,map,res,begin + 1,sb);//撤销选择sb.deleteCharAt(begin);}}
}

五、和为target的组合

LeetCode39：https://leetcode-cn.com/problems/combination-sum/

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：

  • 所有数字（包括 target）都是正整数。
  • 解集不能包含重复的组合。
    在这里插入图片描述
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();List<Integer> list = new ArrayList<>();backtrack(res,list,0,candidates,target);return res;}public void backtrack(List<List<Integer>> res,List<Integer> list,int begin,int[] candidates,int target){
    //结束条件if(target==0){
    res.add(new ArrayList<Integer>(list));return;}for(int i = begin;i < candidates.length;i++){
    //i用于遍历candidates//排除不合法if(target<0){
    break;}//做选择list.add(candidates[i]);//下一决策backtrack(res,list,i,candidates,target - candidates[i]);//撤销上一个选择list.remove(list.size() - 1);}}
}

六、k个数的组合

6.1 数字1-n中k个数的所有组合

class Solution {
    public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<>();if(k <= 0 || n < k){
    return res;}List<Integer> list = new ArrayList<>();backtrack(1,n,k,res,list);return res;}public void backtrack(int idx,int n,int k,List<List<Integer>> res,List<Integer> list){
    if(list.size() == k){
    res.add(new ArrayList<>(list));return;}for (int i = idx; i <= n; i++) {
    list.add(i);// 下一轮搜索，设置的搜索起点要加 1，因为组合数理不允许出现重复的元素backtrack(i + 1, n, k, res, list);list.remove(list.size() - 1);}}
}

6.2 k个数字组合成n的所有组合

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> res = new ArrayList<>();List<Integer> list = new ArrayList<>();if(k<=0 || n<k){
    return res;}backtrack(k,n,1,res,list);return res;}public void backtrack(int k,int n,int index,List<List<Integer>> res,List<Integer> list){
    if(list.size() == k && n == 0){
    res.add(new ArrayList<>(list));return;}for(int i = index;i<=9;i++){
    list.add(i);backtrack(k,n - i,i+1,res,list);list.remove(list.size() - 1);}}
}
  相关解决方案

代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）
Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.