题目：两点之间路径， 求第k条，用回溯法
（0,0）到(M,N) 只能平移或垂直，求第k条比如（2，2，1） 输出 HHVV
（2，2，2） 输出HVHV
我的代码回溯res中只有第一条路径，求找问题出在哪或者其他代码
//m个h，n个v，有h就添加h，没有就添加v，然后回溯
public class ccc {
static List < List<Character> > res=new ArrayList<>();
static char c[]={'h','v'};
public static String solution(int m,int n,int k){
int count[]={m,n};
List<Character> list=new ArrayList<>();
dfs(m,n,count,list,0);
StringBuilder aa=new StringBuilder();
for(int i=0;i<m+n;i++)
aa.append(res.get(k-1).get(i));
return aa.toString();
}
static void dfs(int m,int n,int count[],List<Character> list,int index)
{
if (index==m+n)
{res.add(new ArrayList<>(list));
return;
}
for(int i=0;i<2;i++)
{if(count[i]<=0)
continue;
list.add(c[i]);
count[i]--;
dfs(m,n,count,list,index+1);
list.remove(list.size()-1);
}
return;
}
public static void main(String []args){
System.out.println(solution(3,3,1));
}
}
全部评论
(1) 回帖