排列组合题的框架思路和题目总结

fby0656

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由 liux0656 于 2019-8-26 03:28 编辑

总的来说，都是需要用到回溯法

回溯法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

通用算法思路总结：

初始结果列表。
可能要将数集排序，方便处理重复元素的情况。
调用递归函数。
书写递归函数，先要考虑原点状况，一般就是考虑什么情况下要将当前结果添加到结果列表中。
for循环遍历给定集合所有元素，不同题目区别在于进行循环的条件，具体看例子。每当一个元素添加到当前结果中之后，要再调用递归函数，相当于固定了前缀穷举后面的变化。
调用完之后要将当前结果中最后一个元素去掉，进行下一个循环才不会重复。

算法框架

// 算法框架
public void backtracting(temp){
if("temp是一个结果"){ //结果收集条件
加入结果集;
return;
}
for(j=start;j<= end;j++){
if("不满足加入条件") continue;
temp.add(a); //加入当前元素
backtracting(j+1); //继续进行下一步搜索
temp.remove(a); //回溯的清理工作，把上一步的加入结果删除
}
}
//求存在解的算法框架
public boolean backtracting(temp){
if("temp是一个结果"){ //结果收集条件
加入结果集;
return true;
}
for(j=start;j<= end;j++){
if("不满足加入条件") continue;
temp.add(a); //加入当前元素
if(backtracting(j+1))
return true; //继续进行下一步搜索
temp.remove(a); //回溯的清理工作，把上一步的加入结果删除
return false;
}
}

复制代码

leetcode 题库

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

首先用一个数组把每个数字按键对应的字母存储起来，再把给定的字符串digits拆分成每一个单独的数字做处理。使用一个辅助函数进行处理

private void helper (String digits, int i, StringBuilder cur, List<String> ans);
/*
String digits : 给定的数字组合字符串
int i ：当前（递归）处理的层数
StringBuilder cur ：当前字母组合
List<String> ans ：结果列表
*/

处理过程如下：

取出当前数字，以及该数字按键对应的字母，存为一个char数组curLetters
对curLetters进行遍历，将当前字符加入当前字母组合cur，然后（递归地）处理后一个数字
当层数等于给定字符串digits长度时，将当前字母组合cur加入结果列表ans，删除刚用过的字符（也就是当前字母组合的最后一个字母）
遍历完成后，结果列表ans就是题目要求的结果

private final static String[] digitsToChars =
{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations (String digits) {
List<String> ans = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return ans;
}
doCombination(new StringBuilder(), ans, digits);
return ans;
}
private void doCombination (StringBuilder prefix, List<String> combination, String digits) {
if (prefix.length() == digits.length()) {
combination.add(prefix.toString());
} else {
int curDiggit = digits.charAt(prefix.length()) - '0';
for (char c : digitsToChars[curDiggit].toCharArray()) {
prefix.append(c);
doCombination(prefix,combination,digits);
prefix.deleteCharAt(prefix.length() - 1);
}
}
}

复制代码

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
题目：求出所有有效括号的全排列
思路：针对一个长度为2n的合法排列，第1到2n个位置都满足如下规则：左括号的个数大于等于右括号的个数

设left和right分别为剩余的左右括号数目，则使用递归求解可以分为以下几种情况
1、left>0  可以继续加括号
2、left=0 and right=0 结果收集
3、right>0 还需要满足right>left加入右括号

public class Solution {
public List<String> list = new LinkedList<String>();
public List<String> generateParenthesis(int n) {
if(n == 0)
return list;
generate(n,n,"",list);
return list;
}
public void generate(int left,int right,String res,List<String> list){
if(left == 0 && right == 0){
list.add(res);
return;
}
if(left>0){
generate(left-1,right,res+"(",list);
}
if(right>0 && right>left){
generate(left,right-1,res+")",list);
}
}
}

复制代码

39.Combination Sum

给一个数集和一个数字target，要求返回用数集中数字加和等于target的所有组合（数集中的数可以重复使用）。
DFS + Backtracking。这次是考察重复元素如何处理。依然使用回溯的template

public class Solution {
List<List<Integer>> result;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
result = new ArrayList<>();
Arrays.sort(candidates);
helper(candidates,new ArrayList<>(),target,0);
return result;
}
private void helper(int[] candidates,List<Integer> temp, int remain,int start){
if(remain == 0) {
result.add(new ArrayList<>(temp));
return;
}
for(int i = start;i < candidates.length && remain >= candidates;i++){
int tempRemain = remain - candidates;
if(tempRemain == 0 || tempRemain >= candidates){
temp.add(candidates);
//此处用i，因为可以重复使用元素
helper(candidates,temp,tempRemain,i);
temp.remove(temp.size()-1);
}
}
}
}

复制代码

40.Combination Sum II

给一个数集和一个数字target，要求返回用数集中数字加和等于target的所有组合（数集中的数不可以重复使用）。

这道题不能重复使用，只需要在之前的基础上修改两个地方即可，首先在递归的for循环里加上if(i > start && candidates == candidates[i-1]) continue; 这样可以防止res中出现重复项，然后就在递归调里面的参数换成i+1，这样就不会重复使用数组中的数字了

public class Solution {
List<List<Integer>> result;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
result = new ArrayList<>();
Arrays.sort(candidates);
helper(candidates,new ArrayList<>(),0,target);
return result;
}
private void helper(int[] candidates, List<Integer> temp,int start ,int remain){
if(remain == 0){
result.add(new ArrayList<>(temp));
return;
}
//加入remain判断条件，跳过不必要的循环。
for(int i = start; i < candidates.length && remain >= candidates;i++){
if(i > start && candidates == candidates[i-1]) continue;
int tempRemain = remain - candidates;
if(tempRemain == 0 || tempRemain >= candidates){
temp.add(candidates);
helper(candidates,temp,i+1,tempRemain);
temp.remove(temp.size()-1);
}
}
}
}

复制代码

46.Permuation

给一个数集（无重复元素），返回所有排列。

题目：求出0一串不同的数字的全排列。
思路：1、回溯法深搜，每次都从0------end搜索，不过需要有一个标记数组，来记录哪些已经访问过了，回溯的时候加入的元素以及标记都需要清除。

public class Solution {
List<List<Integer>> result;
public List<List<Integer>> permute(int[] nums) {
result = new ArrayList<>();
if(nums.length == 0) return result;
helper(nums,new ArrayList<>());
return result;
}
private void helper(int[] nums,List<Integer> temp){
if(temp.size() == nums.length)
result.add(new ArrayList<>(temp));
else{
for(int i = 0;i<nums.length;i++){
if(temp.contains(nums)) continue;
temp.add(nums);
helper(nums,temp);
temp.remove(temp.size()-1);
}
}
}
}

复制代码

47. Permutations II

题目：给出含有相同数字的元素，求所有元素的排列。
思路：当nums == nums[i-1] 时候，直接进行下一轮搜索，因为如果进行深搜索的话，得出的结果会和之前的重复。即在if(条件处)限定具体的条件。

public class Solution {
public List<List<Integer>> list = new LinkedList<List<Integer>>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
if(nums.length == 0)
return list;
int[] visited = new int[nums.length+1];
helper(nums,new LinkedList<Integer>(),visited);
return list;
}
public void helper(int[] nums,List<Integer> temp,int[] visited){
if(temp.size() == nums.length){
list.add(new LinkedList<Integer>(temp));
return;
}
for(int i=0;i<nums.length;i++){
if (i>0 && nums==nums[i-1]&&visited[i-1]==1) continue; //具体的限定nums[i-1]==nums则进行下一轮搜索，同时引入标记矩阵。
if(visited == 0){
visited=1;
temp.add(nums);
helper(nums,temp,visited);
visited=0;
temp.remove(temp.size()-1);
}
}
}
}

复制代码

77.Combinations

给一个正整数n,要求返回1-n中k（k<=n）个数所有组合的可能。

public class Solution {
List<List<Integer>> ret;
public List<List<Integer>> combine(int n, int k) {
ret = new ArrayList<>();
if(n<k || n*k==0)
return ret;
int start = 1;
List<Integer> temp = new ArrayList<>();
helper(start,n,k,temp);
return ret;
}
private void helper(int start,int n,int k,List<Integer> temp){
if(temp.size() == k){
ret.add(new ArrayList<Integer>(temp));
} else {
for(int i = start;i<=n;i++){
temp.add(i);
helper(i+1,n,k,temp);
temp.remove(temp.size()-1);
}
}
}
}

复制代码

78.Subsets

给一个数集（无重复数字），要求列出所有子集。

public class Solution {
List<List<Integer>> res;
public List<List<Integer>> subsets(int[] nums) {
res = new ArrayList<>();
if(nums.length == 0)
return res;
List<Integer> temp = new ArrayList<>();
helper(nums,temp,0);
return res;
}
private void helper(int[] nums, List<Integer> temp,int i) {
res.add(new ArrayList<>(temp));
for(int n = i; n < nums.length;n++){
temp.add(nums[n]);
helper(nums,temp,n+1);
temp.remove(temp.size()-1);
}
}
}

复制代码

90.SubsetsII

给一个数集（有重复数字），要求列出所有子集。

public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
helper(list, new ArrayList<>(), nums, 0);
return list;
}
private void helper(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
list.add(new ArrayList<>(tempList));
for(int i = start; i < nums.length; i++){
if(i > start && nums == nums[i-1]) continue; // skip duplicates
tempList.add(nums);
helper(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}

复制代码

131.Panlindrome Partitioning

给定一个回文字符串，要求将其分成多个子字符串，使得每个子字符串都是回文字符串，列出所有划分可能。

public class Solution {
List<List<String>> result;
public List<List<String>> partition(String s) {
result = new ArrayList<>();
helper(new ArrayList<>(),s,0);
return result;
}
private void helper(List<String> temp, String s, int start){
if(start == s.length()){
result.add(new ArrayList<>(temp));
return;
}
for(int i = start; i < s.length();i++){
if(isPanlidrome(s,start,i)){
temp.add(s.substring(start,i+1));
helper(temp,s,i+1);
temp.remove(temp.size()-1);
}
}
}
private boolean isPanlidrome(String s, int low ,int high){
while(low < high)
if(s.charAt(low++) != s.charAt(high--)) return false;
return true;
}
}

复制代码

216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
题目：在1-----9中找出k个元素使其相加等于n
思路：和前面的题类似，回溯下界1 上界9 ，收集的时候限定条件改为 temp.size() == k && target == 0

public class Solution {
List<List<Integer>> res = new LinkedList<List<Integer>>();
public List<List<Integer>> combinationSum3(int k, int n) {
if(k == 0){
return res;
}
hleper(n,k,1,new LinkedList<Integer>());
return res;
}
public void hleper(int sum,int k,int start,List<Integer> templist){
if(sum < 0) return;
if(sum == 0 && templist.size()==k) {
List<Integer> li = new ArrayList<Integer>(templist);
res.add(li);
return;
}
for(int i=start;i<=9;i++){
templist.add(i);
hleper(sum-i,k,i+1,templist);
templist.remove(templist.size()-1);
}
}
}

复制代码

526. Beautiful Arrangement

题目：这道题给了我们1到N，总共N个正数，然后定义了一种优美排列方式，对于该排列中的所有数，如果数字可以整除下标，或者下标可以整除数字，那么我们就是优美排列，让我们求出所有优美排列的个数。
思路：pos表示下标，排列完成，并记录排列位置，visited是否被访问，使用回溯。在进行下一步的搜索的时候条件
为 pos%i ==0 || i%pos == 0 && visited = 0 没有被访问过并且可以被收集。收集条件为pso>n。

class Solution {public:
int countArrangement(int N) {
int res = 0;
vector<int> visited(N + 1, 0);
helper(N, visited, 1, res);
return res;
}
void helper(int N, vector<int>& visited, int pos, int& res) {
if (pos > N) {
++res;
return;
}
for (int i = 1; i <= N; ++i) {
if (visited == 0 && (i % pos == 0 || pos % i == 0)) {
visited = 1;
helper(N, visited, pos + 1, res);
visited = 0;
}
}
}
};

复制代码

698. Partition to K Equal Sum Subsets
Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.

public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(int num:nums)sum += num;
if(k <= 0 || sum%k != 0)return false;
int[] visited = new int[nums.length];
return canPartition(nums, visited, 0, k, 0, 0, sum/k);
}
public boolean canPartition(int[] nums, int[] visited, int start_index, int k, int cur_sum, int cur_num, int target){
if(k==1)return true;
if(cur_sum == target && cur_num>0)return canPartition(nums, visited, 0, k-1, 0, 0, target);
for(int i = start_index; i<nums.length; i++){
if(visited == 0){
visited = 1;
if(canPartition(nums, visited, i+1, k, cur_sum + nums, cur_num++, target))return true;
visited = 0;
}
}
return false;
}

复制代码

784. Letter Case Permutation

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

这个题要求数字保留，字母分成大小写两种。使用回溯法就是分类成数字和字母，字母再分为大写和小写继续。

要注意的一点是不需要使用for循环了。做39. Combination Sum题目的时候使用for循环的目的是能在任意位置起始求和得到目标。本题不需要从任意位置开始。

class Solution {
public:
vector<string> letterCasePermutation(string S) {
vector<string> res;
helper(S, res, {}, 0);
return res;
}
void helper(const string S, vector<string>& res, string path, int start) {
if (start == S.size()) {
res.push_back(path);
return;
}
if (S[start] >= '0' && S[start] <= '9') {
helper(S, res, path + S[start], start + 1);
} else {
helper(S, res, path + (char)toupper(S[start]), start + 1);
helper(S, res, path + (char)tolower(S[start]), start + 1);
}
}
};

复制代码

1079. Letter Tile Possibilities

You have a set of tiles, where each tile has one letter tiles printed on it. Return the number of possible non-empty sequences of letters you can make.

public int numTilePossibilities(String tiles) {
boolean[] used = new boolean[tiles.length()];
HashSet<String> list = new HashSet<>();
dfs(tiles, new StringBuilder(),list,used);
for(String s:list){
System.out.print(s);
}
return list.size();
}
public void dfs(String tiles, StringBuilder s, HashSet<String> list,boolean[] used){
if(s.length() > 0){
list.add(new String(s));
}
for(int i=0;i<tiles.length();i++){
if(!used){
used=true;
s.append(tiles.charAt(i));
dfs(tiles,s,list,used);
s.deleteCharAt(s.length()-1);
used=false;
}
}
}

复制代码

参考链接：
https://blog.csdn.net/yuanmxiang/article/details/68075613
https://zhuanlan.zhihu.com/p/63252392

337845818

看你敲了这么多字就顶一下吧。。

分析backtrack / dfs 不写优化什么的。。

[Leetcode] 排列组合题的框架思路和题目总结

注册一亩三分地论坛，查看更多干货！

评分

浏览过的版块