Leetcode回溯

17. 电话号码的字母组合

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder temp = new StringBuilder();
    String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    void dfs(int index, String digits) {
        if (index == digits.length()) {
            res.add(temp.toString());
            return;
        }
        int num = digits.charAt(index) - '0';
        for (int i = 0; i < map[num].length(); i++) {
            temp.append(map[num].charAt(i));
            dfs(index + 1, digits);
            temp.deleteCharAt(temp.length() - 1);
        }
    }

    public List<String> letterCombinations(String digits) {
        if ("".equals(digits)) {
            return new ArrayList<>();
        }
        dfs(0, digits);
        return res;
    }
}

22. 括号生成

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

    void dfs(int index, int left, int right, int n) {
        //剪枝
        if (left == n + 1 || right > left) {
            return;
        }
        if (index == 2 * n) {
            res.add(temp.toString());
            return;
        }
        temp.append("(");
        dfs(index + 1, left + 1, right, n);
        temp.deleteCharAt(temp.length() - 1);
        temp.append(")");
        dfs(index + 1, left, right + 1, n);
        temp.deleteCharAt(temp.length() - 1);
    }

    public List<String> generateParenthesis(int n) {
        dfs(0, 0, 0, n);
        return res;
    }
}

37. 解数独

class Solution {
    public boolean dfs(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(i, j, c, board) == true) {
                            board[i][j] = c;
                            if (dfs(board) == true) {
                                return true;
                            } else {
                                board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    boolean isValid(int row, int col, char c, char[][] board) {
        int blockRow = 3 * (row / 3);
        int blockCol = 3 * (col / 3);
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == c) {
                return false;
            }
            if (board[row][i] == c) {
                return false;
            }
            if (board[blockRow + i / 3][blockCol + i % 3] == c) {
                return false;
            }
        }
        return true;
    }

    public void solveSudoku(char[][] board) {
        dfs(board);
    }
}

39. 组合总和

组合问题，使用index防止重复。

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

    void dfs(int index, int sum, int target, int[] candidates) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            res.add(new ArrayList<>(temp));
        }
        for (int i = index; i < candidates.length; i++) {
            temp.add(candidates[i]);
            dfs(i, sum + candidates[i], target, candidates);
            temp.remove(temp.size() - 1);
        }
    }

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

40. 组合总和 II

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

    void dfs(int index, int sum, int target, int[] candidates) {
        if (index > candidates.length || sum > target) {
            return;
        }
        if (sum == target) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            if (i - 1 >= index && candidates[i] == candidates[i - 1]) {
                continue;
            }
            temp.add(candidates[i]);
            dfs(i + 1, sum + candidates[i], target, candidates);
            temp.remove(temp.size() - 1);
        }
    }

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

46. 全排列

排列问题使用isVisit数组标记某个元素是否已访问。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    boolean[] isVisit;

    void dfs(int index, int[] nums) {
        if (index == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (isVisit[i] == false) {
                isVisit[i] = true;
                temp.add(nums[i]);
                dfs(index + 1, nums);
                temp.remove(temp.size() - 1);
                isVisit[i] = false;
            }
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        isVisit = new boolean[nums.length];
        dfs(0, nums);
        return res;
    }
}

47. 全排列 II

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    boolean[] isVisit;

    void dfs(int[] nums) {
        if (temp.size() == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //isVisit[i - 1] == false时说明到达同一层相同的地方
            if (i - 1 >= 0 && nums[i] == nums[i - 1] && isVisit[i - 1] == false) {
                continue;
            }
            if (isVisit[i] == false) {
                isVisit[i] = true;
                temp.add(nums[i]);
                dfs(nums);
                temp.remove(temp.size() - 1);
                isVisit[i] = false;
            }
        }
    }

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

51. N 皇后

class Solution {
    List<List<String>> res = new ArrayList<>();
    boolean[] isVisit;
    int[] arr;

    boolean judge(int n) {
        boolean flag = true;
        boolean flag2 = true;//使用标记快速跳出双重for循环
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (Math.abs(i - j) == Math.abs(arr[i] - arr[j])) {//在对角线上
                    flag = false;
                    flag2 = false;
                    break;
                }
            }
            if (flag2 == false) {
                break;
            }
        }
        return flag;
    }

    void dfs(int index, int n) {
        if (index == n + 1) {
            if (judge(n) == true) {
                List<String> list = new ArrayList<>();
                for (int i = 1; i <= n; i++) {
                    int col = arr[i];
                    StringBuilder sb = new StringBuilder();
                    for (int j = 1; j <= n; j++) {
                        if (j != col) {
                            sb.append(".");
                        } else {
                            sb.append("Q");
                        }
                    }
                    list.add(sb.toString());
                }
                res.add(list);
            }
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (isVisit[i] == false) {
                arr[index] = i;
                isVisit[i] = true;
                dfs(index + 1, n);
                isVisit[i] = false;
            }
        }
    }

    public List<List<String>> solveNQueens(int n) {
        isVisit = new boolean[n + 1];
        arr = new int[n + 1];
        dfs(1, n);
        return res;
    }
}

52. N皇后 II

class Solution {
    int res = 0;
    boolean[] isVisit;
    int[] arr;

    boolean judge(int n) {
        boolean flag = true;
        boolean flag2 = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (Math.abs(i - j) == Math.abs(arr[i] - arr[j])) {//在对角线上
                    flag = false;
                    flag2 = false;
                    break;
                }
            }
            if (flag2 == false) {
                break;
            }
        }
        return flag;
    }

    void dfs(int index, int n) {
        if (index == n + 1) {
            if (judge(n) == true) {
                res++;
            }
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (isVisit[i] == false) {
                arr[index] = i;
                isVisit[i] = true;
                dfs(index + 1, n);
                isVisit[i] = false;
            }
        }
    }

    public int totalNQueens(int n) {
        isVisit = new boolean[n + 1];
        arr = new int[n + 1];
        dfs(1, n);
        return res;
    }
}

60. 第k个排列

class Solution {
    boolean[] isVisit;
    StringBuilder res;
    StringBuilder temp = new StringBuilder();
    int count = 0;

    void dfs(int index, int n, int k) {

        if (index == n + 1) {
            count++;
            if (count == k) {
                res = new StringBuilder(temp);
            }
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (isVisit[i] == false) {
                temp.append(i);
                isVisit[i] = true;
                dfs(index + 1, n, k);
                isVisit[i] = false;
                temp.deleteCharAt(temp.length() - 1);
            }
        }
    }

    public String getPermutation(int n, int k) {
        isVisit = new boolean[n + 1];
        dfs(1, n, k);
        return res.toString();
    }
}

77. 组合

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

    void dfs(int index, int n, int k) {
        if (temp.size() == k) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i <= n; i++) {
            temp.add(i);
            dfs(i + 1, n, k);
            temp.remove(temp.size() - 1);
        }
    }

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

78. 子集

可以使用选与不选的dfs。
也可以使用在递归的过程中就把temp加入到res中。

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

    void dfs(int index, int[] nums) {
        if (index == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }
        temp.add(nums[index]);
        dfs(index + 1, nums);
        temp.remove(temp.size() - 1);
        dfs(index + 1, nums);
    }

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

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

    void dfs(int index, int[] nums) {
        if (index == nums.length) {
            return;
        }
        for (int i = index; i < nums.length; i++) {
            temp.add(nums[i]);
            res.add(new ArrayList<>(temp));
            dfs(i + 1, nums);
            temp.remove(temp.size() - 1);
        }
    }

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

79. 单词搜索

class Solution {

    boolean[][] isVisit;
    int[] X = {0, 0, -1, 1};//上下左右
    int[] Y = {-1, 1, 0, 0};

    //对所有规则进行判断
    boolean check(char[][] board, int i, int j, int k, String word) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return false;
        }
        if (isVisit[i][j] == true) {
            return false;
        }
        if (board[i][j] == word.charAt(k)) {
            return true;
        } else {
            return false;
        }
    }


    boolean dfs(char[][] board, int i, int j, int k, String word) {
        if (k == word.length()) {
            return true;
        }
        if (check(board, i, j, k, word) == true) {
            isVisit[i][j] = true;
            for (int z = 0; z < 4; z++) {
                int newI = i + X[z];
                int newJ = j + Y[z];
                if (dfs(board, newI, newJ, k + 1, word) == true) {
                    return true;
                }
            }
            //如果某一点四个方向都不满足条件，改回false
            isVisit[i][j] = false;
        } else {
            return false;
        }
        return false;
    }

    public boolean exist(char[][] board, String word) {
        isVisit = new boolean[board.length][board[0].length];
        //从每一个字母开始出发进行DFS
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                boolean res = dfs(board, i, j, 0, word);
                if (res == true) {
                    return true;
                } else {
                    continue;
                }
            }
        }
        return false;
    }
}

89. 格雷编码

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        int head = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = res.size() - 1; j >= 0; j--) {
                res.add(res.get(j) + head);
            }
            head <<= 1;
        }
        return res;
    }
}

90. 子集 II

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

    void dfs(int index, int[] nums) {
        if (index == nums.length) {
            return;
        }
        for (int i = index; i < nums.length; i++) {
            if (i - 1 >= index && nums[i] == nums[i - 1]) {
                continue;
            }
            temp.add(nums[i]);
            res.add(new ArrayList<>(temp));
            dfs(i + 1, nums);
            temp.remove(temp.size() - 1);
        }
    }

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

93. 复原IP地址

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

    void dfs(int index, String s) {
        if (index == s.length() && segment.size() == 4) {
            StringBuilder t = new StringBuilder();
            for (String se : segment) t.append(se).append(".");
            t.deleteCharAt(t.length() - 1);
            res.add(t.toString());
            return;
        }
        if (index < s.length() && segment.size() == 4) {
            return;
        }

        for (int i = 1; i <= 3; i++) {
            if (index + i > s.length()) {
                return;
            }
            if (i != 1 && s.charAt(index) == '0') {
                return;
            }
            String str = s.substring(index, index + i);
            if (i == 3 && Integer.parseInt(str) > 255) {
                return;
            }
            segment.add(str);
            dfs(index + i, s);
            segment.remove(segment.size() - 1);
        }
    }

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

131. 分割回文串

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

    boolean isPalindromic(String s) {
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }

    void dfs(int index, String s) {
        if (index == s.length()) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            String str = s.substring(index, i + 1);
            if (isPalindromic(str) == true) {
                temp.add(str);
                dfs(i + 1, s);
                temp.remove(temp.size() - 1);
            }
        }
    }

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

132. 分割回文串 II

超时了，思路是正确的。
待优化成动态规划做。

class Solution {
    int res = Integer.MAX_VALUE;
    List<String> temp = new ArrayList<>();

    public boolean isPar(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

    public void dfs(int begin, String s) {
        if (begin == s.length()) {
            res = Math.min(res, temp.size() - 1);
        }
        for (int i = begin; i < s.length(); i++) {
            String sub = s.substring(begin, i + 1);
            if (isPar(sub) == true) {
                temp.add(sub);
                dfs(i + 1, s);
                temp.remove(temp.size() - 1);
            }
        }
    }

    public int minCut(String s) {
        dfs(0, s);
        return res;
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,179评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,229评论 2赞 380
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,032评论 0赞 336
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,533评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,531评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,539评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,916评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,574评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,813评论 1赞 296
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,568评论 2赞 320
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,654评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,354评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,937评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,918评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,152评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,852评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,378评论 2赞 342