LeetCode题解--回溯算法(二)

àì夳堔傛蜴生んèń 2023-06-20 06:25 113阅读 0赞

### 文章目录 ###

*   *  46. 全排列
     *   *  回溯算法
     *  47. 全排列 II
     *   *  回溯算法
     *  77. 组合
     *   *  回溯算法
         *  回溯
         *  剪枝操作
     *  39. 组合总和
     *   *  回溯算法

## 46. 全排列 ##

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

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

### 回溯算法 ###

class Solution {
        
        private void backtrack(List<Integer> permute, List<List<Integer>> permutes, boolean[] visited, int[] nums) {
        
            if (permute.size() == nums.length) {
        
                permutes.add(new ArrayList<>(permute));
                return;
            }
            for (int i = 0; i < visited.length; ++i) {
        
                if (visited[i]) {
        
                    continue;
                }
                visited[i] = true;
                permute.add(nums[i]);
                backtrack(permute, permutes, visited, nums);
                permute.remove(permute.size() - 1);
                visited[i] = false;
            }
        }
        public List<List<Integer>> permute(int[] nums) {
        
            List<List<Integer>> permutes = new ArrayList<>();
            List<Integer> permute = new ArrayList<>();
            boolean[] visited = new boolean[nums.length];
            backtrack(permute, permutes, visited, nums);
            return permutes;
        }
    }

## 47. 全排列 II ##

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

示例:

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

### 回溯算法 ###

在实现上，和 Permutations 不同的是要先排序，然后在添加一个元素时，判断这个元素是否等于前一个元素，如果等于，并且前一个元素还未访问，那么就跳过这个元素。

class Solution {
        
        private void backtrack(List<List<Integer>> permutes, List<Integer> permute, boolean[] visited, int[] nums) {
        
            if (permute.size() == nums.length) {
        
                permutes.add(new ArrayList<>(permute));
                return;
            }
            for (int i = 0; i < nums.length; ++i){
        
                if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
        
                    continue;
                }
                if (visited[i]) {
        
                    continue;
                }
                visited[i] = true;
                permute.add(nums[i]);
                backtrack(permutes, permute, visited, nums);
                permute.remove(permute.size() - 1);
                visited[i] = false;
            }
        }
        public List<List<Integer>> permuteUnique(int[] nums) {
        
            List<List<Integer>> permutes = new ArrayList<>();
            List<Integer> permute = new ArrayList<>();
            Arrays.sort(nums);
            boolean[] visited = new boolean[nums.length];
            backtrack(permutes, permute, visited, nums);
            return permutes;
        }
    }

## 77. 组合 ##

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

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

### 回溯算法 ###

按照上面的套路，不过不是最优的方法。

class Solution {
        
        private void backtrack(List<List<Integer>> combinations, List<Integer> combination, int n, int k, boolean[] visited) {
        
            if (combination.size() == k) {
        
                combinations.add(new ArrayList<>(combination));
                return;
            }
            for (int i = 1; i <= n; ++i) {
        
                if (visited[i]) {
        
                    return;
                }
                visited[i] = true;
                combination.add(i);
                backtrack(combinations, combination, n, k, visited);
                combination.remove(combination.size() - 1);
                visited[i] = false;
            }
        }
        public List<List<Integer>> combine(int n, int k) {
        
            List<List<Integer>> combinations  = new ArrayList<>();
            List<Integer> combination = new ArrayList<>();
            boolean[] visited = new boolean[n + 1];
            backtrack(combinations, combination, n, k, visited);
            return combinations;
        }
    }

### 回溯 ###

稍微优化一下

class Solution {
        
        private void backtrack(List<List<Integer>> combinations, List<Integer> combination, int start, int n, int k) {
        
            if (combination.size() == k) {
        
                combinations.add(new ArrayList<>(combination));
                return;
            }
            for (int i = start; i <= n; ++i) {
        
                combination.add(i);
                backtrack(combinations, combination, i + 1, n, k);
                combination.remove(combination.size() - 1);
            }
        }
        public List<List<Integer>> combine(int n, int k) {
        
            List<List<Integer>> combinations  = new ArrayList<>();
            List<Integer> combination = new ArrayList<>();
            boolean[] visited = new boolean[n + 1];
            backtrack(combinations, combination, 1, n, k);
            return combinations;
        }
    }

### 剪枝操作 ###

关于剪枝操作的讲解部分见[https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/][https_leetcode-cn.com_problems_combinations_solution_hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-]

class Solution {
        
        private void backtrack(List<List<Integer>> combinations, List<Integer> combination, int start, int n, int k) {
        
            if (k == 0) {
        
                combinations.add(new ArrayList<>(combination));
                return;
            }
            for (int i = start; i <= n - k + 1; ++i) {
         // 剪枝操作
                combination.add(i);
                backtrack(combinations, combination, i + 1, n, k - 1);
                combination.remove(combination.size() - 1);
            }
        }
        public List<List<Integer>> combine(int n, int k) {
        
            List<List<Integer>> combinations  = new ArrayList<>();
            List<Integer> combination = new ArrayList<>();
            boolean[] visited = new boolean[n + 1];
            backtrack(combinations, combination, 1, n, k);
            return combinations;
        }
    }

## 39. 组合总和 ##

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

candidates 中的数字可以无限制重复被选取。

说明：

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

输入: candidates = \[2,3,6,7\], target = 7,  
所求解集为:  
\[  
\[7\],  
\[2,2,3\]  
\]  
示例 2:

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

### 回溯算法 ###

class Solution {
        
        private void backtrack(List<Integer> combination, List<List<Integer>> result, int start, int[] candidates, int target) {
        
            if (target == 0) {
        
                result.add(new ArrayList<>(combination));
                return;
            }
            for (int i = start; i < candidates.length; ++i) {
        
                int temp = candidates[i];
                if (temp <= target) {
        
                    combination.add(temp);
                    backtrack(combination, result, i, candidates, target - temp);
                    combination.remove(combination.size() - 1);
                }
            }
        }
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
            List<List<Integer>> result = new ArrayList<>();
            backtrack(new ArrayList<>(), result, 0, candidates, target);
            return result;
        }
    }

[https_leetcode-cn.com_problems_combinations_solution_hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-]: https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/