46. 全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：

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

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

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数互不相同

经典回溯，

套用框架代码

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        permuteHelper(nums);
        return result;
    }

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    private void permuteHelper(int[] nums) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;//直接返回即可，因为我们已经到了路径最末端
        }
        for (int choice : nums) {
            if (path.contains(choice)) {///剪枝
                continue;
            }
            path.add(choice);//做出选择
            permuteHelper(nums); //继续选择
            path.remove(path.size() - 1);//回退
        }
    }
}

注意：

列表添加东西，除了基本数据类型比如int等，加入的都是引用（就是指针）,因此添加要创建新的对象
时间复杂度O(n^2 * n!),空间复杂度O(n)。不对吧，节点数应该是O(n + n(n-1) + n(n-2) + ……+n!)等于O(n!)，每个节点的需要O(1+2+3+……n)=O(n^2)，因此最终是O(n^2*n!)
实际上可以优化。因为path.contains(choice)有一个O(n)的复杂度，使用一个布尔数组代表是否使用更好

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used ;

    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        permuteHelper(nums);
        return result;
    }


    private void permuteHelper(int[] nums) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;//直接返回即可，因为我们已经到了路径最末端
        }
        for (int i = 0;i < nums.length ; i++) {
            int choice = nums[i];
            if (used[i]) {///剪枝
                continue;
            }
            path.add(choice);//做出选择
            used[i] = true;
            permuteHelper(nums); //继续选择
            path.remove(path.size() - 1);//回退
            used[i] = false;
        }
    }
}

时间复杂度降到O(n*n!)

其他方法

原地交换法 (Swap-based Backtracking)(掌握)
1. 定义一个递归函数 backtrack(index, nums)，表示对 nums 数组从 index 位置开始进行全排列。
2. 递归终止条件：当 index 等于数组长度时，说明已经生成了一个完整的排列，将其添加到结果列表中。
3. 遍历与交换：在递归函数内部，从 index 到数组末尾进行遍历（用 i 表示）。将 index 位置的元素与 i 位置的元素进行交换。
4. 递归深入：交换后，固定住 index 位置的元素，对 index + 1 之后的部分继续进行全排列，即调用 backtrack(index + 1, nums)。
5. 回溯：在递归调用返回后，必须将之前交换的元素换回来，以恢复数组状态，确保不影响上一层的循环。这步是回溯的关键。

实际上就是直接借助原本输入数组来记录使用过的元素

import java.util.*;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> numsList = new ArrayList<>();
        for (int num : nums) {
            numsList.add(num);
        }
        permuteHelper(0, numsList, result);
        return result;
    }


    private void permuteHelper(int index, List<Integer> numsList, List<List<Integer>> result) {
        if (index == numsList.size()) {
            result.add(new ArrayList<>(numsList));
            return;
        }

        //循环来确定把哪个数放在index处
        for (int i = index; i < numsList.size(); i++) {
            Collections.swap(numsList, i, index);//做出选择
            permuteHelper(index + 1, numsList, result);//继续选择
            Collections.swap(numsList, i, index);//回溯选择
        }
    }
}

或者直接不用副本更减少空间复杂度

import java.util.Arrays;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        permuteHelper(0, nums, result);
        return result;
    }

    private void permuteHelper(int index, int[] nums, List<List<Integer>> result) {
        if (index == nums.length) {
            // 将 int[] 转换为 List<Integer> 并添加到结果中
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            result.add(permutation);
            return;
        }

        for (int i = index; i < nums.length; i++) {
            swap(nums, i, index);
            permuteHelper(index + 1, nums, result);
            swap(nums, i, index); // 回溯
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
}

注意：

关于根据数组构造List：
1. Collection要实现增删查遍历才算集合，因此数组不是集合，不能直接new ArrayList(Object[])，想要创建最好就是遍历。
关于Arrays.asList()
1. 返回的List固定大小，不支持增删
2. 返回的List是原数组的一个视图，对List的修改直接会修改原数组
3. 基本对象数组无法被正确识别：方法签名是public static List asList(T… a)，基本类型数组比如int[] a,int无法被看作一个对象无法当作泛型，因此会把int[]整体当作一个泛型，得到的是一个List<int[]>,如果一定要用直接使用包装类Intenger[] a

78.子集

https://leetcode.cn/problems/subsets/?envType=study-plan-v2&envId=top-100-liked
给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：

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

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素互不相同

考虑回溯

import java.util.ArrayList;
import java.util.List;

class Solution {
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        subsetsHelper(nums,0,result,path);
        return result;
    }

    private void subsetsHelper(int[] nums,int start, List<List<Integer>> result,List<Integer> path) {
        result.add(new ArrayList<>(path));//不return，因为可能要继续
        
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            subsetsHelper(nums, i+1, result,path);//相信sunsetsHelper能够把path已有的作为前缀，从start开始，找出所有可能的组合并放入result，并且最终完成回溯使得path只剩下前缀的状态
            path.remove(path.size() - 1);
        }
    }
}

时间复杂度：一共2^n个子集，每个子集都要被复制一次O(l),(kC(n,k),k从0加到n),这个结果就是O(n2^n。可以分为子集平均长度是n/2,因为每个子集的相对于整个集合的补集也是整个集合的补集，和为n，可以划分成2^n/2个组合，每个组合长度是n，因此总长度n2^n/2，平均长度n/2

空间复杂度：path O(n),result O(2^n),栈O(n),不算结果最终是O(n)

迭代法

对于一个集合，例如 S = {1, 2, 3}，它的所有子集可以被精确地分为两类：

不包含 最后一个元素 3 的子集。
包含最后一个元素 3 的子集。

第一类：不包含 3 的子集，其实就是 {1, 2} 的所有子集。
第二类：包含 3 的子集，可以通过获取 {1, 2} 的所有子集，然后给每一个子集都添加上元素 3 来得到。

所以，如果我们知道了 P(n-1)（前 n-1 个元素的所有子集），我们就可以通过以下两步得到 P(n)（前 n 个元素的所有子集）：

P(n) 包含 P(n-1) 的所有内容。
P(n) 还包含 P(n-1) 中每个子集都加上第 n 个元素后形成的新子集。

步骤

初始化结果集 result，并首先放入一个空集 []。
遍历 nums 数组中的每一个数字 num。
对于 result 中已经存在的每一个子集，都创建一个新的子集，将 num 添加进去，然后将这个新子集也加入 result。
遍历完所有数字后，result 就包含了所有可能的子集。

import java.util.ArrayList;
import java.util.List;

class Solution {
   public List<List<Integer>> subsets(int[] nums) {
      List<List<Integer>> result = new ArrayList<>();
      result.add(new ArrayList<>());
      for (int num : nums) {
          int currentSize = result.size();
         for (int i = 0; i < currentSize; i++) {//这里不能使用for-each循环，因为for—each不允许被迭代对象被修改。
            List<Integer> newSub = new ArrayList<>(result.get(i)); 
            newSub.add(num);
            result.add(newSub);
         }
      }
      return result;
   }

}

时间还是O(n*2^n),空间O(n)

17.电话号码的字母组合

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envType=study-plan-v2&envId=top-100-liked
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = “23”
输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
示例 2：

输入：digits = “”
输出：[]
示例 3：

输入：digits = “2”
输出：[“a”,”b”,”c”]

提示：

0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

思考：

先建立一个列表List<List>把映射关系存起来。然后分别遍历嵌套循环。

实际上很难嵌套循环，长度是可变的。可以回溯，如果到头了就撤销选择。

映射关系更好的是使用Map<Intenger，String>

空间复杂度是O(n)，时间复杂度O(nk^n)(k是一个数字对应的字母数)（最差的话就是O(n4^n)）

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {

   public List<String> letterCombinations(String digits) {
      Map<Character, String> map = new HashMap<>();
      List<String> result = new ArrayList<>();

      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");
      if (digits.isEmpty()){//注意String比较不能用==
          return new ArrayList<>();
      }
      StringBuilder path = new StringBuilder();
      backTrack(map,result,path,digits,0);
      return result;
   }

   private void backTrack(Map<Character,String> map,List<String> result,StringBuilder path,String digits,int start){
       if (path.length() == digits.length()){
           result.add(new String(path));
           return;
       }
      String thisLoopString = map.get(digits.charAt(start));
      for (int j = 0; j < thisLoopString.length(); j++) {
         char c = thisLoopString.charAt(j);
         path.append(c);//做出选择
         backTrack(map,result,path,digits,start+1);//相信backTrack能够把以当前path已经有的为前缀，把从start+1位开始的所有组合得到，并且和前缀结合起来添加到result，并且回溯到只剩下前缀。
         path.deleteCharAt(path.length()-1);//销毁选择
      }
      
   }
}

回溯实际上也是深度优先

下面可以用迭代广度优先

迭代
1. 初始化：创建一个队列（LinkedList 在 Java 中常被用作队列），并向其中添加一个空字符串 ""。这个空字符串是所有组合的起点。
2. 遍历数字：遍历输入的数字字符串 digits 中的每一个数字。
3. 逐层构建：对于每个数字，遍历当前队列中已有的所有部分组合。
  - 从队列中取出一个部分组合。
  - 获取当前数字对应的所有字母。
  - 将取出的部分组合与每个字母拼接，形成新的、更长的组合。
  - 将这些新组合放入队列的末尾。
4. 完成：当遍历完所有数字后，队列中剩下的就是所有最终的完整组合。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Map;

class Solution {

   public List<String> letterCombinations(String digits) {
      Map<Character, String> map = new HashMap<>();
      Queue<String> queue = new LinkedList<>();

      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");
      if (digits.isEmpty()) {//注意String比较不能用==
         return new ArrayList<>();
      }
      queue.offer("");
      for (int i = 0; i < digits.length(); i++) {
         String thisLoopString = map.get(digits.charAt(i));
         int thisQueueNum = queue.size();
         for (int j = 0; j < thisQueueNum; j++) {
            String newStringToEdit = queue.poll();
            for (int k = 0; k < thisLoopString.length(); k++) {
               String newString = newStringToEdit + thisLoopString.charAt(k);
               queue.offer(newString);
            }
         }
      }
      return new ArrayList<>(queue);
   }

}

复杂度：

时间：一共k^n中情况，每种情况需要创建一个新的字符串长度为n，因此是O(n*k^n)

空间：O(n*4^n)

39.组合总和

https://leetcode.cn/problems/combination-sum/description/?envType=study-plan-v2&envId=top-100-liked
给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素互不相同
1 <= target <= 40

考虑回溯

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
   public List<List<Integer>> combinationSum(int[] candidates, int target) {
      List<List<Integer>> result = new ArrayList<>();
      List<Integer> path = new ArrayList<>();
      Arrays.sort(candidates);
      backTrace(result,path,candidates,target,0);
      return result;
   }

   private void backTrace(List<List<Integer>> result, List<Integer> path, int[] candidates, int sumNowNeed,int start) {
      if (sumNowNeed == 0) {
         result.add(new ArrayList<>(path));
         return;
      }
      for (int i = start; i < candidates.length; i++) {
          sumNowNeed = sumNowNeed - candidates[i];
          if (sumNowNeed<0){
              sumNowNeed = sumNowNeed + candidates[i];
              return;//剪枝，只要candidates有序，目前的已经导致sunNowNeed小于0，那么选取更大的肯定sumNowNeed更小。
          }
         path.add(candidates[i]);//start可以保障不重复，只要candidates有序
         backTrace(result, path, candidates, sumNowNeed, i);//相信back Trace能把以当前前缀为开头的，候选索引从candidates的i开始(不能比上一轮选择的更靠前），的所有满足的情况加入result，并且回溯到只剩下当前前缀
         path.remove(path.size()-1);
         sumNowNeed += candidates[i];//回溯记得把所有量都回溯，不要只记得回溯path
      }
   }
}

时间复杂度:不考虑剪枝的情况，递归树最大高度是target/min_val记为D,第一次有n个选择，第二层每个节点也是n个选择，因此整个树节点数目是O(n^(target/min)),非叶节点操作是O（1），叶节点操作是O(D),叶节点数目是S（解的数目），因此最终是O(N^D+s*D)

空间复杂度：递归调用栈是和path都是O(D)

22.括号生成

https://leetcode.cn/problems/generate-parentheses/description/?envType=study-plan-v2&envId=top-100-liked
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例 1：

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

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

提示：

1 <= n <= 8

如果使用回溯，一共n对括号，意味着左括号右括号各有n个。同时要确保，任何时候left的数目要大于等于right，否则剪枝；同时左括号数目不能大于n，否则剪枝。当path的长度为2n记录结果返回。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> generateParenthesis(int n) {
        StringBuilder path = new StringBuilder();
        List<String> result = new ArrayList<>();
        char[] candidates = new char[] {'(',')'};
        backTrace(result,path,n,candidates,0,0);
        return result;
    }
    private void backTrace(List<String> result,StringBuilder path,int n,char[] candidates,int left_num,int right_num){
        if (path.length() == 2*n){
            result.add(new String(path));
            return;
        }
        for (char charChosed : candidates) {
            if (charChosed == '('){
                left_num++;
            }else {
                right_num++;
            }
            if (left_num >= right_num && left_num <= n && right_num <= n) {//剪枝最好写成条件，但要记得把left_num和right_num给恢复
                path.append(charChosed);
                backTrace(result, path, n, candidates, left_num, right_num);
                path.deleteCharAt(path.length() - 1);
            }
            if (charChosed == '(') {
                left_num--;
            } else {
                right_num--;
            }


        }

    }
    
}

时间复杂度：不考虑剪枝：4^n*n；考虑剪枝这是个卡特兰数，( 4^n / n^(3/2) ) * n

空间复杂度：调用栈和path都是O(n),不考虑结果就是O(N)

动态规划法

任意一个有效括号开头必定是 “(“,因此必定对应一个”)”.

因此任意一个有效组合可以分为如下结构：

(A)B,A和B都要是有效括号，并且A和B 的括号对数和要是n-1.

设A有i对，则B有n-1-i对

记i为状态，dp[i]为i对括号的所有可能组合。

dp[i] = (dp[j])dp[i-1-j],j从0遍历到i-1

边界条件dp[0] = {“”}

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> generateParenthesis(int n) {
        List<List<String>> dp = new ArrayList<>();
        List<String> dp0 = new ArrayList<>();
        dp0.add("");
        dp.add(dp0);
        for (int i = 1; i <= n; i++) {
            List<String> dp_i = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                List<String> dp_j = dp.get(j);
                List<String> dp_i_1_j = dp.get(i-1-j);
                for (String stringA : dp_j) {
                    for (String stringB : dp_i_1_j) {
                        dp_i.add("("+stringA+")"+stringB);
                    }
                }
            }
            dp.add(dp_i);
        }
        return dp.get(n);
    }
}

79.单词搜索

https://leetcode.cn/problems/word-search/description/?envType=study-plan-v2&envId=top-100-liked

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [[‘A’,’B’,’C’,’E’],[‘S’,’F’,’C’,’S’],[‘A’,’D’,’E’,’E’]], word = “ABCCED”
输出：true
示例 2：

输入：board = [[‘A’,’B’,’C’,’E’],[‘S’,’F’,’C’,’S’],[‘A’,’D’,’E’,’E’]], word = “SEE”
输出：true
示例 3：

输入：board = [[‘A’,’B’,’C’,’E’],[‘S’,’F’,’C’,’S’],[‘A’,’D’,’E’,’E’]], word = “ABCB”
输出：false

提示：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

考虑回溯

path记录，只要path和word相等，exitWord改为true并返回。尝试的选择可以先遍历一个字符串数组up、down、left、right依次选择向哪里走，如果索引越界则撤销选择。(索引不能越界)

path长度要小于word

path对应的字母要和word相同

class Solution {
    public boolean exist(char[][] board, String word) {
        int[][] direction = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                boolean[][] used = new boolean[board.length][board[0].length];
                StringBuilder path = new StringBuilder();
                path.append(board[i][j]);
                used[i][j] = true;
                backTrace(board,word,path,direction,new int[]{i,j},used);
                if (exitWord == true){
                    return exitWord;
                }
            }
        }
        return exitWord;
    }
    private boolean exitWord = false;//java按值传递，所以这个变量似乎只能作为成员变量了
    private void backTrace(char[][] board,String word,StringBuilder path,int[][] direction,int[] start,boolean [][] used){
        if (path.toString().equals(word)){
            exitWord = true;
            return;
        }
        for (int[] direct : direction) {
            start[0] += direct[0];
            start[1] += direct[1];
            if (start[0] < board.length && start[0] >= 0 && start[1] >= 0 && start[1] < board[0].length && path.length() < word.length() && !used[start[0]][start[1]] && board[start[0]][start[1]] == word.charAt(path.length())){//剪枝，记得稍后恢复start
                used[start[0]][start[1]] = true;
                path.append(board[start[0]][start[1]]);//做出选择
                backTrace(board,word,path,direction,start,used);//继续选择
                path.deleteCharAt(path.length()-1);
                used[start[0]][start[1]] = false;
            }
            start[0] -= direct[0];
            start[1] -= direct[1];
        }
    }
}

上面是正确的，但是代码写的很乱。下面是优化

直接返回true或者false
不用path，直接传入k表示正在寻找word第k个字符
可以在回溯中直接创建新的行列坐标，不用手动再次恢复了

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        int[][] direction = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        boolean[][] visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(backTrace(board,word,0,i,j,visited,direction)){
                    return true;
                }
            }
        }
        return false;
        
    }
    private boolean backTrace(char[][] board,String word,int k ,int row,int col,boolean[][] visted,int[][] direction){
        if (board[row][col] != word.charAt(k)){
            return false;//剪枝
        }
        if (k == word.length()-1 && board[row][col] == word.charAt(k)){
            return true;//成功基线
        }
        //做出选择
        visted[row][col] = true;
        //继续探索
        for (int[] dir : direction) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            if (newRow >= 0 && newRow < board.length && newCol>=0 &&newCol < board[0].length && !visted[newRow][newCol]){
                if (backTrace(board,word,k+1,newRow,newCol,visted,direction)){//契约是：backTrace从给定的行列坐标开始，自由探索字符使得和word中从k+1开始的字符都一一相等（不能使用visted中用过的），如果全部相等则返回true，否则false
                    return true;
                }
            }
        }
        visted[row][col] = false;//撤销选择
        //全部探索完还没有为真的就返回false
        return false;
    }
}

131.分割回文字符

https://leetcode.cn/problems/palindrome-partitioning/description/?envType=study-plan-v2&envId=top-100-liked
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

示例 1：

输入：s = “aab”
输出：[[“a”,”a”,”b”],[“aa”,”b”]]
示例 2：

输入：s = “a”
输出：[[“a”]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

可以回溯

回文字符串的判断，可以双指针，从中间开始向两侧移动，每个字符都相等就是回文，O(n)的成本

剪枝：不好减

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        List<String> path = new ArrayList<>();
        backTrace(result,path,0,s);
        return result;
    }
    private void backTrace(List<List<String>> result,List<String> path,int start,String s){
        if (start == s.length()){//所有字符都被加入了已经
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            String newSub = s.substring(start,i);//subString包含起点不含结束的点，因此i小于等于s.length;sunString(start,start)会返回空字符，因此i从start+1开始
            if (isPalindrome(newSub)){//剪枝
                path.add(newSub);
                backTrace(result,path,i,s);//newSub不包含索引为i（结束点）的字符，因此，start应该从i开始
                path.remove(path.size()-1);
            }
        }
    }
    private boolean isPalindrome(String s){
        int left = 0;
        int right = s.length()-1;
        while (left < right){
            if (s.charAt(left) != s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

实际上来说，中间可能遇到很多重复判断。[i,j)的子串可能会多次判断，耗费O(k),可以使用二维数组把遇到的结果存起来，记忆化搜索

考虑引入一个数组memo[start][end],代表[start,end]子串，值为0意味着未计算，值为1意味着是回文，值为2意味着不是回文

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        List<String> path = new ArrayList<>();
        int[][] memo = new int[s.length()][s.length()];
        backTrace(result,path,0,s,memo);
        return result;
    }
    private void backTrace(List<List<String>> result,List<String> path,int start,String s,int[][] memo){
        if (start == s.length()){//所有字符都被加入了已经
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            if (isPalindrome(s,start,i-1,memo) == 1){//剪枝
                String newSub = s.substring(start,i);//subString包含起点不含结束的点，因此i小于等于s.length;sunString(start,start)会返回空字符，因此i从start+1开始
                path.add(newSub);
                backTrace(result,path,i,s,memo);//newSub不包含索引为i（结束点）的字符，因此，start应该从i开始
                path.remove(path.size()-1);
            }
        }
    }
    private int isPalindrome(String s, int left, int right, int[][] memo){
        if (memo[left][right] != 0) {
            return memo[left][right];
        }
        // 注意：这里不再创建子串，而是直接在原字符串s上用left和right指针判断
        int i = left;
        int j = right;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                memo[left][right] = 2; // 不是回文
                return 2;
            }
            i++;
            j--;
        }
        memo[left][right] = 1; // 是回文
        return 1;
    }
}

时间复杂度:O(n*2^n).最坏情况任何一种划分都符合要求。一共有2^(n-1)个划分方案（两个数中间的空位可以划一刀或者不划一刀），复制花费O(n),每种方案每个子串都要判断是否是回文，耗费复杂度O(n)

空间复杂度:O(n^2),调用栈最深是O(n),记忆数组O(n^2)

可以先dp动态规划预处理

可以直接构建dp[start][end]表代表[start,end]是否为回文(为了方便我们首位都取)

dp[i][j]为回文，显然需要首尾字符相同，并且除了首位外的字符串是个回文。

因此，dp[i][j] = (char[i]==char[j])&&(dp[i+1][j-1])

我们只需要填j>=i的部分

也就是主对角线及其上方

边界条件：i==j,true.

注意递推的步长是2，每次i-j都减小2，因此部分无法递推到i==j

第二个边界条件：

i-j == 1,此时真假就是char[i] == char[j]

填充顺序从左到右，从下到上

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        List<String> path = new ArrayList<>();
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = s.length()-1; i >= 0 ; i--) {
            dp[i][i] = true;
        }
        for (int i = 0; i <= s.length() - 2; i++) {
            dp[i][i+1] = s.charAt(i)==s.charAt(i+1);
        }
        for (int i = s.length()-1; i >= 0 ; i--) {
            for (int j = i+2; j < s.length(); j++) {
                dp[i][j] = (s.charAt(i)==s.charAt(j))&&(dp[i+1][j-1]);
            }
        }
        backTrace(result,path,0,s,dp);
        return result;
    }
    private void backTrace(List<List<String>> result,List<String> path,int start,String s,boolean[][] dp){
        if (start == s.length()){//所有字符都被加入了已经
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            String newSub = s.substring(start,i);//subString包含起点不含结束的点，因此i小于等于s.length;sunString(start,start)会返回空字符，因此i从start+1开始
            if (dp[start][i-1]){//剪枝
                path.add(newSub);
                backTrace(result,path,i,s,dp);//newSub不包含索引为i（结束点）的字符，因此，start应该从i开始
                path.remove(path.size()-1);
            }
        }
    }
}

时间复杂度同上
空间复杂度同上

51.N皇后

https://leetcode.cn/problems/n-queens/description/?envType=study-plan-v2&envId=top-100-liked
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：

输入：n = 1
输出：[[“Q”]]

提示：

1 <= n <= 9

每一行只能放一个皇后

每行的防止位置要保障列、两条斜线线处没有皇后（剪枝条件）

主斜线线：row - col = c;副斜线：row + col = c;

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        List<String> plan = new ArrayList<>();
        backTrace(result,plan,n,0);
        return result;
    }

    private void backTrace(List<List<String>> result, List<String> plan, int n,int row) {
        if (plan.size() == n) {
            result.add(new ArrayList<>(plan));
            return;
        }
        for (int i = 0; i < n; i++) {
            StringBuilder thisRow = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (j==i){
                    thisRow.append('Q');
                }
                else {
                    thisRow.append('.');
                }
            }
            plan.add(new String(thisRow));//做出选择
            if (!thisColTwoQ(plan,i,row,n) && !thisFirstSlashTwoQ(plan,i,row,n) && !thisSecondSlashTwoQ(plan,i,row,n)){
                backTrace(result,plan,n,row+1);//继续探索下一行
            }
            plan.remove(plan.size()-1);

        }
    }
    private boolean thisColTwoQ(List<String> plan,int col,int row,int n){
        for (int i = row - 1; i >= 0 ; i--) {
            String s = plan.get(i);
            if (s.charAt(col) == 'Q'){
                return true;
            }
        }
        return false;
    }
    private boolean thisFirstSlashTwoQ(List<String> plan,int col,int row,int n){
        int c = row - col;//col = row-c
        for (int i = row - 1; i >= 0 ; i--) {
            int j = i - c;
            if (j < 0 || j > n-1){
                break;
            }
            String s = plan.get(i);
            if (s.charAt(j) == 'Q'){
                return true;
            }
        }
        return false;
    }
    private boolean thisSecondSlashTwoQ(List<String> plan, int col, int row ,int n){
        int c = row + col;//col = c - row
        for (int i = row - 1; i >= 0 ; i--) {
            int j = c - i;
            if (j < 0 || j > n - 1){
                break;
            }
            String s = plan.get(i);
            if (s.charAt(j) == 'Q'){
                return true;
            }
        }
        return false;

    }
}

上面的解法是正确的

但是剪枝的逻辑可以进一步优化。

目前的剪枝调用多个函数，每个函数都要再次遍历一次之前已有的所有行

可以直接使用三个布尔数组来记录对应的行、对角线是否已经有Q

import java.util.*;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        List<String> plan = new ArrayList<>();
        boolean[] col = new boolean[n];
        boolean[] diag1 = new boolean[2*n];
        boolean[] diag2 = new boolean[2 * n];
        backTrace(result,plan,n,0,col,diag1,diag2);
        return result;
    }

    private void backTrace(List<List<String>> result, List<String> plan, int n,int row,boolean[] col,boolean[] diagonals1,boolean[] diagonals2) {
        if (plan.size() == n) {
            result.add(new ArrayList<>(plan));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!col[i] && !diagonals1[row-i+n-1] && !diagonals2[row+i]){
                StringBuilder thisRow = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if (j==i){
                        thisRow.append('Q');
                    }
                    else {
                        thisRow.append('.');
                    }
                }
                col[i] = true;
                diagonals1[row - i + n - 1] = true;//保证索引大于等于0
                diagonals2[row + i] = true;
                plan.add(new String(thisRow));//做出选择

                backTrace(result,plan,n,row+1,col,diagonals1,diagonals2);//继续探索下一行
                
                plan.remove(plan.size()-1);
                col[i] = false;
                diagonals1[row - i + n - 1] = false;//保证索引大于等于0
                diagonals2[row + i] = false;

            }

        }
    }
}

空间复杂度：布尔数组都是O(n),调用栈O(n),总共O(n)

时间复杂度：

递归树节点：第一行N,第二行N-1等等（不考虑剪枝），因此一共O(N!)个节点，每个节点本地操作O(N),对于叶节点S（N），有O(N^2)的复制，所以总的是O(N!*N+S(N)*N^2)

下面是官方解答

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = 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>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }

    public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            List<String> board = generateBoard(queens, n);
            solutions.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(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                queens[row] = -1;
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }

    public 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;
    }
}

主要不同在于：

使用Set来记录重复，天然支持负数索引
使用int[] queens,queens[row]=col,找到答案后一次性生成棋盘

还可以进一步优化

使用位运算状态压缩

class Solution {
    public List<List<String>> solveNQueens(int n) {
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        List<List<String>> solutions = new ArrayList<List<String>>();
        solve(solutions, queens, n, 0, 0, 0, 0);
        return solutions;
    }

    public void solve(List<List<String>> solutions, int[] queens, int n, int row, int columns, int diagonals1, int diagonals2) {
        if (row == n) {
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
        } else {
            int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
            while (availablePositions != 0) {
                int position = availablePositions & (-availablePositions);
                availablePositions = availablePositions & (availablePositions - 1);
                int column = Integer.bitCount(position - 1);
                queens[row] = column;
                solve(solutions, queens, n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
                queens[row] = -1;
            }
        }
    }

    public 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;
    }
}

知识补充：

补码：目前计算机的有符号整数一般都是使用补码表示的。它是为了处理两个相反数之和应当为0，并且0只能有一个表示。这样可以节省计算机资源。最高位是符号位，0表示0或者正数。正数补码是自己，负数补码是，负数的绝对值按位取反后+1

关于上面代码的一些解释

第1步: `availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));`

这行代码在寻找当前行所有安全的列。我们把它拆成三小步：

(columns | diagonals1 | diagonals2)
- | 是按位或 (OR) 运算。只要三个整数中任意一个的某一位是 1，结果的该位就是 1。
- 所以，这个表达式计算出了一个总的攻击范围。结果中所有为 1 的位，都代表当前行不能放皇后的列。
- 例 (N=8): 假设 columns = 00010000, diagonals1 = 00100000, diagonals2 = 00000100。
- OR 的结果是 00110100。这表示第2、4、5列是危险的。
~(...)
- ~ 是按位非 (NOT) 运算，它会把所有的 0 变成 1，1 变成 0。
- 我们对上面的危险位置 00110100 取反，得到 11001011。
- 现在，结果中所有为 1 的位，就代表当前行可以放皇后的安全列。
((1 << n) - 1) & (...)
- 1 << n：对于 n=8，1 << 8 是 100000000 (一个1后面8个0)。
- (1 << n) - 1：100000000 - 1 结果是 11111111 (连续n个1)。这是一个掩码。
- 为什么要用掩码？因为 ~ 运算会把一个整数的所有位（比如32位）都取反，我们只关心代表棋盘的低 n 位。用 & (按位与) 操作，可以屏蔽掉高位无关的 1。
- 最终，availablePositions 就是一个整数，其中为 1 的位精确地对应了当前行所有能安全放置皇后的列。

第3步: `position = availablePositions & (-availablePositions);` (lowbit技巧)

这是一个非常经典的位运算技巧，叫做 lowbit。它的作用是只保留一个数最右边的那个 1，其余位都清零。

例: availablePositions 是 01011000。
-availablePositions 在计算机中是用补码表示的，等于 ~availablePositions + 1，结果是 10101000。
01011000 & 10101000 的结果是 00001000。
看，我们成功地分离出了最右边的一个可放置位置！position 现在就代表了我们这次要尝试放置皇后的那个点。

第4步: `availablePositions = availablePositions & (availablePositions - 1);`

这也是一个经典技巧，作用是消除一个数最右边的那个 1。

例: availablePositions 是 01011000。
availablePositions - 1 是 01010111。
01011000 & 01010111 的结果是 01010000。
最右边的 1 被干掉了！这样，在下一次 while 循环中，lowbit 技巧就会抓到下一个可用的位置（现在最右边的那个 1）。

通过第3步和第4步的配合，这个 while 循环可以不重不漏地、高效地遍历所有可放置皇后的位置，而不需要一个 for 循环从头到尾检查。

第5步: `int column = Integer.bitCount(position - 1);`

现在我们有了 position，比如 00001000 (十进制是8)，但我们需要的是列的索引号，也就是 3。怎么转换？

position 永远是2的幂，只有一个位是 1。
position - 1 会得到一个低位全是 1 的数。例如 8 - 1 = 7，二进制是 00000111。
Integer.bitCount() 方法会计算一个数有多少个 1。00000111 中有3个 1。
这个 1 的数量，正好就是我们想要的列索引！

46. 全排列

78.子集

17.电话号码的字母组合

39.组合总和

22.括号生成

79.单词搜索

131.分割回文字符

51.N皇后

第1步: availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));

第3步: position = availablePositions & (-availablePositions); (lowbit技巧)

第4步: availablePositions = availablePositions & (availablePositions - 1);

第5步: int column = Integer.bitCount(position - 1);

第1步: `availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));`

第3步: `position = availablePositions & (-availablePositions);` (lowbit技巧)

第4步: `availablePositions = availablePositions & (availablePositions - 1);`

第5步: `int column = Integer.bitCount(position - 1);`