回溯 - 《leetcode》

组合
括号生成
- 括号生成
全排列
搜索
- 岛屿数量
图
- 所有可能的路径

使用DFS实现
步骤

确定函数参数
确认终止条件
确定回溯条件

先修改temp 回溯后撤回
对具体情况进行剪枝

组合

子集
子集II
组合
组合总和
组合总和II

全排列

全排列
全排列II
字符串全排列
字母大小写全排列

括号生成

括号生成

搜索

数独
N皇后
分割字符串
二进制手表

子集是完全回溯单点不返回
子集2是子集1+剪枝右子树
组合是子集+剪枝长度
组合总数是完全回溯+单点返回

组合

子集

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

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

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

    public void back(int cur, int[] nums) {
        if(cur == nums.length) {
            res.add(new ArrayList(t));
            return;
        }
        t.add(nums[cur]);
        back(cur + 1, nums);
        t.remove(t.size() - 1);
        back(cur+1, nums);
    }
}

//解法II  二进制枚举
//以001  即选择num[2]
class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}

子集II

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

在子集基础上进行剪枝操作（排序+右子树剪枝）

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

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

    public void back(boolean x, int cur, int[] nums) {
        if(cur == nums.length) {
            res.add(new ArrayList(t));
            return;
        } 
        t.add(nums[cur]);
        back(true, cur + 1, nums);
        t.remove(t.size()-1);
        if(x && cur > 0 && nums[cur] == nums[cur-1]) return; 
        back(false, cur + 1, nums);    
    }
}

组合

输入：n = 4, k = 2
输出：
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4] ]

在子集基础上对长度进行剪枝
剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp

class Solution {
    List<List<Integer>> res = new ArrayList();
    List<Integer> t = new ArrayList();
    public List<List<Integer>> combine(int n, int k) {
        back(1, n, k);
        return res;
    }
    public void back(int cur, int n, int k) {

        if(t.size() + (n - cur + 1) < k) return;
        if(t.size() == k){
            res.add(new ArrayList(t));
            return;
        }

        t.add(cur);
        back(cur+1, n, k);
        t.remove(t.size()-1);
        back(cur+1, n, k);
    }
}

组合总数

输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]

在子集基础上进行单节点回溯

class Solution {
   List<List<Integer>> res = new ArrayList();
   List<Integer> t = new ArrayList();
   public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(0, target, candidates);
        return res;
    }

    public void dfs(int cur, int target, int[] nums) {
        if (cur == nums.length) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList(t));
            return;
        }
        // 直接跳过
        dfs(cur+1, target, nums);
        // 选择当前数
        if (target - nums[cur] >= 0) {
            t.add(nums[cur]);
            dfs(cur, target - nums[cur], nums);
            t.remove(t.size() - 1);
        }
    }
}

组合总数II

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

class Solution {
    List<int[]> freq = new ArrayList<int[]>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> sequence = new ArrayList<Integer>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int num : candidates) {
            int size = freq.size();
            if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
                freq.add(new int[]{num, 1});
            } else {
                ++freq.get(size - 1)[1];
            }
        }
        dfs(0, target);
        return ans;
    }

    public void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }

        dfs(pos + 1, rest);

        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; ++i) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.remove(sequence.size() - 1);
        }
    }
}

括号生成

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

class Soluition {

    List<String> res = new ArrayList();
    public List<String> generateParenthesis(int n) {
        back(new StringBuilder(), 0, 0, n);
        return res;
    }

    public void back(StringBuilder cur, int left, int righht, int n) {
        if(cur.length() == n << 1) {
            res.add(cur.tostring());
            return;
        }
        if(left < n) {
            cur.append('(');
            backl(cur, left+1, right, n);
            cur.deleteCharAt(cur.lengtgh()-1);
        }
        if(right < n) {
            cur.append(')');
            back(cur, left, righht+1, n);
            cur.deletChatAt(cur.length()-1);
        }
    }
}

全排列

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

全排列类似于一颗多叉树的遍历。你可以选择一个分支，遍历后撤回

解法I

解法II
回溯 - 图4


//1 使用标记数组
//  使用boolean 标记第几个在前  可实现字典序
class Solution {
    boolean[] is;
    int[] nums;
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> t = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        this.is = new boolean[nums.length];
        this.nums = nums;
        backtracking();
        return res;
    }
    void backtracking() {
        if(t.size() == nums.length) {
            res.add(new ArrayList(t));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(is[i]) {
                continue;
            }

            path.add(nums[i]);
            is[i] = true;
            backtracking();
            is[i] = false;
            path.remove(t.size() - 1);
        }
    }
}

//2 使用数组交换的方式进行全排列 
//  建立一个ArrayList添加元素依次调整123位
class Solution {
    private List<List<Integer>> res = new ArrayList();
    private List<Integer> t = new ArrayList();
    private int[] nums;
    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        for(int num : nums) {
            t.add(num);
        }
        back(0);
        return res;
    }
    public void back(int cur){
        if(cur == nums.length) {
            res.add(new ArrayList(t));
            return;
        }

        for(int i = cur; i < nums.length; i++) {
            Collections.swap(t, cur, i);
            back(cur + 1);
            Collections.swap(t, cur, i);
        }

    }
}

全排列II

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

剪枝右子树

//可以同时解决全排列问题
//与全排列相比只增加一个(i > 0 && nums[i] == nums[i - 1] && !is[i - 1]) 剪枝右子树
class Solution {
    boolean[] is;
    int[] nums;
    List<List<Integer>> res =  new ArrayList<List<Integer>>();
    List<Integer> t = new ArrayList<Integer>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        this.is = new boolean[nums.length];
        Arrays.sort(nums);
        this.nums = nums;
        backtrack();
        return res;
    }

    public void backtrack() {
        if (t.size() == nums.length) {
            res.add(new ArrayList(t));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (is[i] || (i > 0 && nums[i] == nums[i - 1] && !is[i - 1])) {
                continue;
            }
            t.add(nums[i]);
            is[i] = true;
            backtrack();
            is[i] = false;
            t.remove(t.size()-1);
        }
    }
}

//剪枝不完全 不能解决0019 因为  9010   i=1  i=3 而我们比较相邻的
class Solution {
    private List<List<Integer>> res = new ArrayList();
    private List<Integer> t = new ArrayList();
    private int[] nums;
    private boolean[] is;
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        for(int num : nums) {
            t.add(num);
        }
        is = new boolean[nums.length];
        back(0);
        return res;
    }
    public void back(int cur){
        if(cur == nums.length) {
            res.add(new ArrayList(t));
            return;
        }
        for(int i = cur; i < nums.length; i++) {
            if(i > 0 && t.get(i) == t.get(i-1) && !is[i-1]) {
                continue;
            }
            Collections.swap(t, cur, i);
            is[i] = true;
            back(cur + 1);
            is[i] = false;
            Collections.swap(t, cur, i);
        }

    }
}

字母大小写全排列

输入：S = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]

class Solution {
    List<String> list = new ArrayList();
    public List<String> letterCasePermutation(String s) {
        getStr(0, s, new StringBuffer());
        return list;
    }

    public void getStr(int index, String s, StringBuffer sb){
        if(index == s.length()){
            list.add(sb.toString());
            return;
        }
        char ch = s.charAt(index);
        sb.append(ch);
        getStr(index + 1, s, sb);
        sb.deleteCharAt(sb.length() - 1);

        // 判断是否是字符，如果是，则转换大小写
        if(!Character.isDigit(ch)){
            ch = (char)(ch - 'a' >= 0 ? ch - 32 : ch + 32);
            sb.append(ch);
            getStr(index + 1, s, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]


class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;

    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap,String digits, int index, StringBuffer combination) {
          if(index == digits.length()) {
              combinations.add(combination.toString());
          } else{
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }

        }
    }
}

字符串的排列

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

class Solution {
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toArray();
        dfs(0);
        return c.toArray(new String(c.size()));
    }
    void dfs(int x) {
        if(x == c.length -1){
            res.add(String.valueOf(c));
            return;
        }
        HashSet<Character> set = new HashSet();
        for(int i = x; i< c.length; i++) {
            if(set.contains(c[i])) continue;
            set.add(c[i]);
            swap(i, x);
            dfs(x+1);
            swap(i, x);
        }
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }

}

搜索

岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

class Solution {
    public int numIslands(char[][] grid) {
      int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    public void dfs(char[][] grid, int i, int j){
        if(i < 0|| j < 0 || i >= grid.length|| j >= grid[0].length || grid[i][j] == '0') return;
        grid[i][j] ='0';
        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
    }

}

图

所有可能的路径

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

class Solution {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    Deque<Integer> stack = new LinkedList();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        stack.addLast(0);
        dfs(graph, 0, graph.length - 1);
        return ans;
    }

    public void dfs(int[][] graph, int x, int n) {
        if (x == n) {
            ans.add(new ArrayList<Integer>(stack));
            return;
        }
        for (int y : graph[x]) {
            stack.addLast(y);
            dfs(graph, y, n);
            stack.removeLast();
        }
    }
}