回溯5.排列序列
程序员文章站
2022-05-21 23:21:55
...
返回第k个序列,序列是共有n个元素的集合中的全排列
首先这是一个排列问题,用used,然后序列中没有重复的元素,只是对集合进行排列而已,当进行到第k个时候直接返回即可。
class Solution {
String res="";
int count=1;
public String getPermutation(int n, int k) {
boolean[] used=new boolean[n];
StringBuffer buffer = new StringBuffer();
core(n,k,used,buffer,0);
return res;
}
public void core(int n,int k,boolean[] used,StringBuffer temp,int depth){
if(res!=""){
return; //依靠这个来摆脱到k之后的回溯。
}
if(depth==n){
if(count==k){
res=temp.toString(); //到k则给res赋值
}else{
count++;
//不到k则count++,但不用管s
}
return; //到k就要return
}
for(int i=0;i<n;i++){//i从0到n,有n个分支
if(!used[i]){//没有遍历过才进入
temp.append(i+1);
used[i]=true;
core(n,k,used,temp,depth+1);
temp.deleteCharAt(temp.length() - 1);
used[i]=false;
}
}
}
}
推荐阅读
-
python回溯法实现数组全排列输出实例分析
-
python算法(输入一个包含重复数字的序列返回不重复的全排列)
-
给定一个序列求指定位数的排列组合数
-
C语言:保持数列有序:有n(约定n<=100)个整数,已经按照从小到大顺序排列好,现在另外给一个整数x,请将该数插入到序列中,并使新的序列仍然有序。
-
【必备算法】回溯:LeetCode题 78. 子集,46. 全排列,51. N皇后,37. 解数独
-
python回溯法实现数组全排列输出实例分析
-
python算法(输入一个包含重复数字的序列返回不重复的全排列)
-
【LeetCode】842. 将数组拆分成斐波那契序列【回溯+剪枝】
-
【回溯法】leetcode组合、排列
-
5.算法设计与分析__回溯算法