组合

77. 组合

https://leetcode.cn/problems/combinations/

for循环 i确定开头(第一层)的数字循环里面进行递归确定第二层的数字当遍历到第k层就结束
使用tag标记下一层的开头数字

使用公式 n-i+1 + list.size() >= k 进行减枝
n-i+1 表示剩下可选的数字，list.size() 表示当前已选择的数，加起来不能小于 k

class Solution {
    List<Integer> list = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        dfs(n, k, 1);
        return res;
    }

    public void dfs(int n, int k, int tag) {
        if(list.size() == k) {
            res.add(new ArrayList<>(list));
            return;
        }

        for(int i = tag;  n-i+1 + list.size() >= k; i++) {
            list.add(i);
            dfs(n, k, i+1);
            list.remove(list.size()-1);
        }
    }
}

216. 组合总和 III

https://leetcode.cn/problems/combination-sum-iii/
和上一题一样 for循环确定第一层的数字里面递归确定下一层的数字也可以跳过该层（也就是回溯list.remove(list.size()-1);）
只是加了一个和要为n 的条件
剪枝 i <= n && i <= 9

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(k, 1, n);
        return res;
    }

    public void dfs(int k, int begin, int n) {
        if(list.size() == k && n == 0) {
            res.add(new ArrayList<Integer>(list));
            return;
        }

        for(int i = begin; i <= n && i <= 9; i++) {
            list.add(i);
            dfs(k, i+1, n-i);
            list.remove(list.size()-1);
        }
    }
}

17. 电话号码的字母组合

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
for循环决定第一层数组的元素选择（例如{a, b, c}中选哪一个）
里面的递归表示进入下层数组（{d,e, f}）

class Solution {
    String[][] arr = new String[][]{ 
                    {"a","b","c"},{"d","e","f"},
                    {"g","h","i"},{"j","k","l"},{"m","n","o"},
                    {"p","q","r","s"},{"t","u","v"},{"w","x","y","z"} };
    List<String> res = new ArrayList<>();
    List<String> list = new ArrayList<>();


    public List<String> letterCombinations(String digits) {
        int k = digits.length();
        if(k != 0) dfs(k, 0, digits);
        return res;
    }

    public void dfs(int k, int begin, String digits) {
        if(list.size() == k) {
            StringBuffer str = new StringBuffer();
            int size = list.size();
            
            for(int i = 0; i <= size - 1; i++) {
                str.append(list.get(i));                
            }
            res.add(new String(str));
            return;
        }

        for(int i = 0; i <= arr[digits.charAt(begin)-'2'].length-1; i++) {
            list.add(arr[digits.charAt(begin)-'2'][i]);
            dfs(k, begin+1, digits);
            list.remove(list.size()-1);
        }
    }
}

39. 组合总和（可重复选取）

https://leetcode.cn/problems/combination-sum/description/
for循环确定第一层的数字里面递归确定下一层的数字
确定下一层的 begin不需要+1，因为可以重复选取

剪枝： target >= candidates[i] 先将数组排序之后只要当前的要选取的数大于还需要的总和 target 就结束
因为已经从小到大排序了当前的数大于target 那么之后数组中的数也一定也大于

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, 0);
        return res;
    }

    public void dfs(int[] candidates, int target, int begin) {
        if(target == 0) res.add(new ArrayList<>(list));
        if(target <= 0) return;

        for(int i = begin; i <= candidates.length-1 && target >= candidates[i]; i++) {
            list.add(candidates[i]);
            dfs(candidates, target-candidates[i], i);
            list.remove(list.size()-1);
        }
    }
}

40. 组合总和 II （有重复元素）

https://leetcode.cn/problems/combination-sum-ii/description/

和组合总和思路一致
重点就是同层的元素选取不能重复选取所以加入一个条件 i > begin && candidates[i] == candidates[i-1] 同层遇到相同的元素就跳过（前提要相见数组排序）

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, 0);
        return res;
    }

    public void dfs(int[] candidates, int target, int begin) {
        if(target == 0) res.add(new ArrayList<>(list));
        if(target <= 0) return;

        for(int i = begin; i <= candidates.length-1 && target >= candidates[i]; i++) {
            if(i > begin && candidates[i] == candidates[i-1]) continue;

            list.add(candidates[i]);
            dfs(candidates, target - candidates[i], i+1);
            list.remove(list.size()-1);
        }
    }
}

分割

切割问题类似组合问题

131. 分割回文串

https://leetcode.cn/problems/palindrome-partitioning/description/

for循环选择如何分割如：a,ad 还是 aa,b 还是 aab,
递归进入下一层选择上一层分割后右边的部分如何分割如：a,a,d 还是 a,ad,
逗号,代表分割代码中begin表示
当begin到达字符串最后面代表结束

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> list = new ArrayList<>();

    public List<List<String>> partition(String s) {
        dfs(s, 0);
        return res;
    }
 
    public void dfs(String s, int begin) {
        if(begin == s.length()) {
            res.add(new ArrayList<>(list));
            return;
        } 

        for(int i = begin+1; i <= s.length(); i++) {
            if(!isHui(s, begin, i-1)) continue;

            list.add(s.substring(begin, i));
            dfs(s, i);
            list.remove(list.size()-1);
        }
    }

    public boolean isHui(String str, int l, int r) {
        while(l < r) {
            if(str.charAt(l) != str.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}

93. 复原 IP 地址

https://leetcode.cn/problems/restore-ip-addresses/description/

class Solution {
    List<String> res = new ArrayList<>();
    StringBuffer strBuff = new StringBuffer();

    public List<String> restoreIpAddresses(String s) {
        dfs(s, 0, 0);
        return res;
    }

    public void dfs(String s, int begin, int num) {
        if(num == 4) {
            if(begin == s.length()) res.add(strBuff.deleteCharAt(begin+3).toString());
            return;   
        }

        for(int i = begin+1; i <= s.length() && i <= begin+3; i++) {
            String str = s.substring(begin, i);
            if(!isTrue(str)) continue;

            strBuff.append(str+".");
            dfs(s, i, num+1);
            strBuff.delete(begin+num, i+num+1);
        }
    } 

    public boolean isTrue(String str) {
        if(Integer.parseInt(str) > 255  || (str.length() > 1 && str.charAt(0) == '0')) return false;
        return true;
    }
}

子集

和组合问题没有什么区别，唯一不同就是加入res时候是每个节点都加入res中，而组合问题是将叶子节点才加入res，需要一个判断if

78. 子集

https://leetcode.cn/problems/subsets/description/

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    public void dfs(int[] nums, int begin) {
        res.add(new ArrayList<>(list));

        for(int i = begin; i <= nums.length-1; i++) {
            list.add(nums[i]);
            dfs(nums, i+1);
            list.remove(list.size()-1);
        }  
    }
}

90. 子集 II (有重复元素)

https://leetcode.cn/problems/subsets-ii/description/
同层的元素选取不能重复选取，加一个条件 if(i > begin && nums[i] == nums[i-1])

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs(nums, 0);
        return res;
    }

    public void dfs(int[] nums, int begin) {
        res.add(new ArrayList<>(list));

        for(int i = begin; i <= nums.length-1; i++) {
            if(i > begin && nums[i] == nums[i-1]) continue;

            list.add(nums[i]);
            dfs(nums, i+1);
            list.remove(list.size()-1);
        } 
    }
}

491. 递增子序列（排除同层重复元素方法2）

https://leetcode.cn/problems/non-decreasing-subsequences/
因为要求子序列，所以不能再通过将数组进行排序，然后i > begin && nums[i] == nums[i-1]来排除同层重复元素
这道题如果通过使用res.contians() 来排除重复list会超时
所以 只能使用一个集合或者数组来记录同层的元素是否重复

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    
    public List<List<Integer>> findSubsequences(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    public void dfs(int[] nums, int begin) {
        if(list.size() >= 2) res.add(new ArrayList<>(list));

        List<Integer> temp = new ArrayList<>();
        for(int i = begin; i <= nums.length-1; i++) {
            if(temp.contains(nums[i]) || list.size() > 0 && nums[i] < list.get(list.size()-1)) continue;

            temp.add(nums[i]);
            list.add(nums[i]);
            dfs(nums, i+1);
            list.remove(list.size()-1);
        }
    }
}

排列

46. 全排列

https://leetcode.cn/problems/permutations/description/

和组合的区别在于结果的每个list里面的元素不是按照nums数组元素的顺序可以是无序的，
所以，下一层的元素选择只需要判断是否已经选取过，
可以使用数组判断也可以使用list里面的方法直接进行判断。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        dfs(nums);
        return res;
    }

    public void dfs(int[] nums) {
        if(list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }

        for(int i = 0; i <= nums.length-1; i++) {
            if(list.contains(nums[i])) continue;

            list.add(nums[i]);
            dfs(nums);
            list.remove(list.size()-1);
        }
    }    
}

47. 全排列 II (排除同层重复元素)

https://leetcode.cn/problems/permutations-ii/description/

首先要排除同层重复元素，其次下一层要排除已经选过的元素
使用一个数组arr 如果该元素被选就将该位置标记为true，回溯时标记回false
进入下一层后先判断同层元素是否重复使用 i > 0 && nums[i] == nums[i-1]（要先将数组排序）, 并且 arr[i-1] == false 证明上一个相同元素和自己是同一层，如果以上条件都满足，就continue；
如何判断当前元素上几层是否选过 arr[i] == false 如果选过就跳过。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    boolean [] arr;
 
    public List<List<Integer>> permuteUnique(int[] nums) {
        arr = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums);
        return res;
    }

    public void dfs(int[] nums) {
        if(list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }

        for(int i = 0; i <= nums.length-1; i++) {
            if(i > 0 && nums[i] == nums[i-1] && arr[i-1] == false) continue;
            if(arr[i] == false) {
                arr[i] = true; 
                list.add(nums[i]);
                dfs(nums);
                list.remove(list.size()-1);
                arr[i] = false;
            }
        }
    }
}

深度搜索

组合