算法分析 [回溯算法] 2019-02-26

1. 回溯算法

分析
框架 这个框架的好处是,

1. 之前的值都能用temp保存住
2. 并且使用temp做剪纸函数
3. 若是存在重复数，需要去重，先排序，然后nums[i] == nums[i-1]做去重

public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> rs = new ArrayList<>();
        backtrack(rs, new ArrayList<>(), nums, 0);
        return rs;
    }
    
    private void backtrack(List<List<Integer>> rs, List<Integer> temp, int []nums, int start) {
        // 这里是回溯的剪纸函数
        rs.add(new ArrayList<>(temp));
        for(int i=start; i<nums.length; i++) {
            temp.add(nums[i]);
            backtrack(rs, temp, nums, i+1);
            temp.remove(temp.size()-1);
        }
    }

1.1 从集合总进行组合，等于目标值，求组合数

39. 组合总和(对内部值进行累加，值可以重复使用) Combination Sum medium
法1. 回溯法 时间复杂度O(n^2)
每次进入函数

1. 先判断是否值<0，return
2. 值==0，add(new ArrayList<>(temp));
3. 每次循环完成，，才进行++

40. 组合总和 II(对内部值进行累加，值不可重复使用) Combination Sum II medium
(重要)先将集合排序
每次循环前先入列表，每次循环进入都+1，进入循环前先判断当前i>idx && nums[i] == nums[i-1]
这个步骤可以去重判断，之所以可以这么用，是因为一开始先排序了
递归初次已经处理了，顺序遍历的时候与前值相等就可以略去

1.2 获取集合中所有的子集

78. 子集(无重叠数值) Subsets medium
法1. 回溯法 时间复杂度O(n^2)
每次循环前先入列表，每次循环进入都++

90. 子集(有重叠数值，且子集不能重复) Subsets II medium
法1. 回溯法 时间复杂度O(n^2)
先将集合排序
每次循环前先入队列，每次循环进入都++，进入循环前先判断当前i>idx && nums[i] == nums[i-1] // 这个步骤可以去重判断，之所以可以这么用，是因为一开始先排序了

1.3 从集合总进行组合，组合不能重复

46. 全排列 Permutations medium
法1. 回溯法 时间复杂度O(n^2)
每次循环，通过temp判断是否已经在上次处理过对应的值
法2. 回溯法 时间复杂度O(nlogn)
每次循环，交换start和当前i所在的位置，递归的时候从第idx+1开始

            for(int i=idx; i<nums.length; i++) {
                swap(nums, idx, i);
                dp(rs, nums, idx+1);
                swap(nums, i, idx);
            }

47. Permutations II

17. 输入数组返回所有对应字母的组合 Letter Combinations of a Phone Number
法1. 回溯法 时间复杂度O(n^2)
每次获取数字对应的字符列表，对字符列表进行回溯

1.4 从字符串中分割回纹数

131. 分割回纹数 Palindrome Partitioning medium
法1. 回溯法 时间复杂度O(n^2)
每个字符串按照substring()切割，并判断是否是回纹数，是回纹数入列表，否者