参考： 回溯法详解
    一、以计算集合元素全排列为例，标准的回溯法如下：
    示例：输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

    1. class Solution {
    2.     public List<List<Integer>> permute(int[] nums) {
    3.         List<List<Integer>> result = new ArrayList<>();
    4.         backTrack(result,new ArrayList<Integer>(),nums); //回溯
    5.         return result;
    6.     }
    8.     private void backTrack(List<List<Integer>> result, List<Integer> path, int[] nums){
    9.         if(path.size()==nums.length){
    10.             result.add(new ArrayList<>(path));//一定要重新声明的个集合
    11.             return;
    12.         }
    13.         for(int n : nums){
    14.             if(path.contains(n)) continue;
    15.             path.add(n);
    16.             backTrack(result, path, nums); //继续
    17.             path.remove(path.size()-1); //回溯
    18.         }
    19.     }
    20. }

    二、以计算集合元素子集为例，标准回溯法如下：
    示例：输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

    1. class Solution {
    2.     public List<List<Integer>> subsets(int[] nums) {
    3.         List<List<Integer>> result = new ArrayList<>();
    4.         backTrack(result, new ArrayList<>(), nums, 0);
    5.         return result;
    6.     }
    8.     private void backTrack(List<List<Integer>> result, List<Integer> path, int[] nums, int idx){
    9.         result.add(new ArrayList<>(path)); //因为是求子集，因此这里不需要判断一条路径是否走完，每个子路径都是一个子集
    10.         for(int i=idx; i< nums.length; i++){
    11.             path.add(nums[i]);
    12.             backTrack(result, path, nums, i+1); //子集不能包含重重复元素，需要在依靠下标依次选取后续元素
    13.             path.remove(path.size()-1);
    14.         }
    15.     }
    16. }
    题目 思路 备注
    电话号码的字母组合 map存储每个数字的字符列表
    回溯法为构建每条路径字符串
    全排列 标准的回溯法
    分隔回文串 回溯法，f[i][j]的值表示回溯法 - 图1子串是否是回文串，0:未知，1:是，-1:不是.
    从第0个字符开始dfs，向右延展，逐步判断每一个分隔的子串是不是回文串
    image.png    		 image.png
    删除无效的括号 思路：有效的括号遵循这样的规律：
    - 从左看起，在任意位置，左括号数量总大于等于右括号数量；从右看起时类似
    - 最终左右括号数量必相同

    ——因此当过程中某个字符打破上述规则的话，就需删除该字符
    回溯法的具体步骤：
    1. 先算出一共要删除多少’(‘及’)’
    1. 从第一个字符开始判断，每当遇到一个’(‘，如果可删，则尝试删之， 右括号类似
    1. 终止条件：要删的左右括号均为0
    优化点： a. 剩余字符少于欲删字符量; b. 连续的同向括号，只需处理第一个即可，其它的不需要重复去。 | 关键代码1——判断括号是否有效：image.png
    关键代码2——统计待删除的左右括号数：
    image.png
    关键代码三——不断递归尝试删括号
    image.png | |
    | | | | | | | | | | | | | | | | | | | | | | | | | | |