leetcode部分回溯及搜索算法题目汇总及解答-搜云库技术团队

1、子集问题

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

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

import java.util.ArrayList;
import java.util.List;

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

    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null || nums.length == 0)
            return lists;
        dfs(nums, new ArrayList<>(), 0);
        return lists;
    }

    private void dfs(int[] nums, List<Integer> list, int len) {
        lists.add(new ArrayList<>(list));
        for (int i = len; i < nums.length; i++) {
            list.add(nums[i]);
            dfs(nums, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

2、子集问题Ⅱ

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]


import java.util.*;

class Solution {
    List<List<Integer>> lists = new ArrayList<>();
    Set<List<Integer>> set = new HashSet<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums == null || nums.length == 0)
            return lists;
        Arrays.sort(nums);
        dfs(nums,new ArrayList<>(),0);
        return lists;
    }

    private void dfs(int[] nums, List<Integer> list, int start) {
        if (!set.contains(list)) {
            set.add(new ArrayList<>(list));
            lists.add(new ArrayList<>(list));
        }
        for (int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            dfs(nums, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

3、组合总数

import java.util.ArrayList;
import java.util.List;

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

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0 || target < 0)
            return lists;
        dfs(new ArrayList<>(), candidates, target, 0);
        return lists;
    }

    private void dfs(List<Integer> list, int[] candidates, int target, int start) {
        if (target < 0)
            return;
        if (target == 0){
             lists.add(new ArrayList<>(list)); **//注意递归条件这里不要写在循环里面**
             return;
        }
        for (int i = start; i < candidates.length; i++) {
            list.add(candidates[i]);
            dfs(list, candidates, target - candidates[i], i);  //这里继续从i开始，数字可以复用
            list.remove(list.size() - 1);
        }
    }
}

4、组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

import java.util.*;

class Solution {
    List<List<Integer>> lists = new ArrayList<>();
    Set<List<Integer>> set = new HashSet<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0 || target < 0)
            return lists;
        Arrays.sort(candidates);
        dfs(candidates,new ArrayList<>(),target,0);
        return lists;
    }

    private void dfs(int[] candidates, List<Integer> list, int target, int start) {
        if (target < 0)
            return;
        if (target == 0){
            if(!set.contains(list)){
                set.add(new ArrayList<>(list));
                lists.add(new ArrayList<>(list));
                return;
            }
        }

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

5、字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

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

import java.util.*;

class Solution {
    Set<String> set = new HashSet<>();
    public String[] permutation(String s) {
        dfs(s,new StringBuilder(),new boolean[s.length()]);
        return set.toArray(new String[set.size()]);
    }

    private void dfs(String s, StringBuilder sb, boolean[] isVisited) {
        if(sb.length() == s.length()){
            set.add(sb.toString());
            return;        //这里写return
        }       
        for (int i = 0; i < s.length(); i++) {
            if (isVisited[i])
                continue;
            isVisited[i] = true;
            sb.append(s.charAt(i));

            dfs(s,sb,isVisited);

            isVisited[i] = false;
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

6、电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入：”23″
输出：[”ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

import java.util.ArrayList;
import java.util.List;
class Solution {
    List<String> list = new ArrayList<>();
    String[] strs;
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0)
            return list;
        strs = new String[]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        dfs(0, digits, new StringBuilder());
        return list;
    }

    private void dfs(int len, String digits, StringBuilder sb) {
        if (sb.length() == digits.length()){
             list.add(sb.toString());
             return;    //这里不加return会出错
        }      
        for (char c : strs[digits.charAt(len) - '2'].toCharArray()) {
            sb.append(c);
            dfs(len + 1, digits, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

7、全排列问题

import java.util.ArrayList;
import java.util.List;

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

    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0)
            return lists;
        dfs(nums, new ArrayList<>(),new boolean[nums.length]);
        return lists;
    }

    public void dfs(int[] nums, List<Integer> list, boolean[] isVisited) {
        if (list.size() == nums.length){
            lists.add(new ArrayList<>(list));
            return;
        }     
        for (int i = 0; i < nums.length; i++) {
            if (isVisited[i])
                continue;
            isVisited[i] = true;
            list.add(nums[i]);
            dfs(nums, list, isVisited);
            list.remove(list.size() - 1);
            isVisited[i] = false;
        }
    }
}

8、全排列II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2] 输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    Set<List<Integer>> set = new HashSet<>();
    private List<List<Integer>> lists;
    public List<List<Integer>> permuteUnique(int[] nums) {
         lists = new ArrayList<>();
        dfs(nums,new ArrayList<>(),new boolean[nums.length]);
        return lists;

    }
    private void dfs(int[] nums,List<Integer> list, boolean[] isVisited){
        if(list.size() == nums.length){
            if(!set.contains(list)){
                 set.add(new ArrayList<>(list));
                 lists.add(new ArrayList<>(list));
                 return;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if(isVisited[i])
                continue;
            list.add(nums[i]);
            isVisited[i] = true;
            dfs(nums,list,isVisited);
            list.remove(list.size()-1);
            isVisited[i] = false;
        }
    }
}

9、二叉树中和为某一值的路径

import java.util.ArrayList;
import java.util.List;

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

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null)
            return lists;
        dfs(root,sum,new ArrayList<>());
        return lists;
    }

    public void dfs(TreeNode root, int sum, List<Integer> list) {
        if (root == null)
            return;  //return只能放在这里
        list.add(root.val);
        sum -= root.val;
        if (root.left == null && root.right == null && sum == 0){
              lists.add(new ArrayList<>(list)); 
             //这里不能加return
        }  
        dfs(root.left, sum, list);
        dfs(root.right, sum, list);

        list.remove(list.size() - 1);
    }
}

10、二叉树中的路径和Ⅱ(字节面试)

public class PathSumI {
    private static int result;
    public static int sumTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        StringBuilder path = new StringBuilder();
        dfs(root, path);
        return result;
    }

    private static void dfs(TreeNode root, StringBuilder path) {
        if(root == null)
            return;
        path.append(root.val);
        if (root.left == null && root.right == null) {
            result += Integer.valueOf(path.toString());
        }
        dfs(root.left, path);
        dfs(root.right, path);
        path.deleteCharAt(path.length() - 1);
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(8);
        node1.left = node2;
        node1.right = node3;
        System.out.println(sumTree(node1));
    }
}

11. 括号生成


数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

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

import java.util.ArrayList;
import java.util.List;

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

    public List<String> generateParenthesis(int n) {
        if (n == 0)
            return list;
        dfs(n, n, new StringBuilder());
        return list;
    }

    public void dfs(int left, int right, StringBuilder sb) {
        if (left > right)
            return;
        if (left == 0 && right == 0) {
            list.add(sb.toString());
        }

        if (left > 0) {
            dfs(left - 1, right, sb.append("("));
            sb.deleteCharAt(sb.length() - 1); //每个条件成立都要回溯
        }
        if (right > 0) {
            dfs(left, right - 1, sb.append(")"));
            sb.deleteCharAt(sb.length() - 1); //每个条件成立都要回溯
        }
    }
}

注意这样写是错误的:
    if (left > 0) {
            dfs(left - 1, right, sb.append("("));
        }
        if (right > 0) {
            dfs(left, right - 1, sb.append(")"));
        }
        sb.deleteCharAt(sb.length() - 1);

        原因是可能两次条件都成立，但是只回溯了一次

总结

组合和排列不是一类问题，组合或者子集类的问题，子集中的元素前后顺序不区分，排列区分，故在排列中需要标记位，标记是否访问过, 对于二叉树则需要注意return的位置。

追加

12.岛屿数量

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

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

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

示例 1:

输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1
示例 2:

输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

class Solution {
    int count = 0;

    public int numIslands(char[][] grid) {
        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+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }
}

文章永久链接：https://tech.souyunku.com/27971

leetcode部分回溯及搜索算法题目汇总及解答