hot100的回溯起始篇

hot100的回溯起始篇

全排列(046)

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        int length = nums.length;
        List<Integer> currentPath = new ArrayList<>(length);
        for (int num : nums) {
            currentPath.add(num);
        }

        backtrack(0, currentPath, length);
        return result;
    }

    private void backtrack(int index, List<Integer> currentPath, int length) {
        if (index == length - 1) {
            result.add(new ArrayList(currentPath));
            return;
        }

        for (int i = index; i < length; i++) {
            Collections.swap(currentPath, index, i);
            backtrack(index + 1, currentPath, length);
            Collections.swap(currentPath, index, i);
        }
    }
}

• 分析

依据排列组合的原理，可知答案的数量为输入数组长度的阶乘。例如，当输入数组长度n为3时，第一个位置有3种选择情况，第二个位置有2种选择情况，第三个位置有1种选择情况。关键代码部分：

for (int i = index; i < length; i++) {
    Collections.swap(currentPath, index, i);
    backtrack(index + 1, currentPath, length);
    Collections.swap(currentPath, index, i);
}

子集(078)

class Solution {
    List<List<Integer>> resultSet = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<Integer> currentPath = new ArrayList<>();
        backtrack(0, currentPath, nums, n);
        return resultSet;
    }

    private void backtrack(int index, List<Integer> currentPath, int[] nums, int length) {
        if (index == length) {
            resultSet.add(new ArrayList(currentPath));
            return;
        }
        currentPath.add(nums[index]);
        backtrack(index + 1, currentPath, nums, length);
        currentPath.remove(currentPath.size() - 1);
        backtrack(index + 1, currentPath, nums, length);
    }
}

• 分析

这是一种典型的类似背包问题的思路，对于每个元素存在选或者不选两种处理方式。

电话号码的字母组合(017)

class Solution {
    String[] digitMapping = new String[] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    List<String> resultStr = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        int n = digits.length();
        if (!digits.isEmpty()) {
            backtrack(0, digits, new StringBuilder(), n);
        }
        return resultStr;
    }

    private void backtrack(int index, String digits, StringBuilder builder, int length) {
        if (index == length) {
            resultStr.add(builder.toString());
            return;
        }

        char currentChar = digits.charAt(index);
        currentChar -= '0';
        for (char ch : digitMapping[currentChar].toCharArray()) {
            builder.append(ch);
            backtrack(index + 1, digits, builder, length);
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}

• 分析

这是较为基础的回溯应用场景。

组合总和(039)

class Solution {
    List<List<Integer>> combinationResult = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<Integer> currentPath = new ArrayList<>();
        backtrack(0, target, currentPath, candidates);
        return combinationResult;
    }

    private void backtrack(int index, int target, List<Integer> currentPath, int[] candidates) {
        if (target == 0) {
            combinationResult.add(new ArrayList(currentPath));
            return;
        }

        if (index == candidates.length || target < candidates[index]) {
            return;
        }

        backtrack(index + 1, target, currentPath, candidates);
        currentPath.add(candidates[index]);
        backtrack(index, target - candidates[index], currentPath, candidates);
        currentPath.remove(currentPath.size() - 1);
    }
}

• 分析

可称作是一种类似原地背包的回溯方法，不过目前不确定是否有这样的特定定义。

括号生成(022)

class Solution {
    List<String> parenthesisResult = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        StringBuilder builder = new StringBuilder();
        backtrack(n, n, builder);
        return parenthesisResult;
    }

    private void backtrack(int leftCount, int rightCount, StringBuilder builder) {
        if (leftCount > rightCount || leftCount < 0 || rightCount < 0) {
            return;
        }
        if (leftCount == 0 && rightCount == 0) {
            parenthesisResult.add(builder.toString());
            return;
        }

        backtrack(leftCount - 1, rightCount, builder.append('('));
        builder.deleteCharAt(builder.length() - 1);
        backtrack(leftCount, rightCount - 1, builder.append(')'));
        builder.deleteCharAt(builder.length() - 1);
    }
}

• 分析

属于典型的回溯操作，并且受到括号的限制条件，即右括号的数量不能超过左括号的数量