问题
给出字符串”abc”计算其全排列
如abc,acb,bac,bca,cab,cba
思路
使用递归方法,每次确定一个未使用的字符,再递归寻找下一个未使用的字符,直到生成字符串长度与原来的长度相同,就返回,每次返回之后,要把这次的字符取消标记
伪代码
1 2 3 4 5 6 7 8 9 10 |
def find(int len,int position,string s): if(s.len == len) result.add(s);//添加到结果集 return;//返回 for(int j = position;j < len;j++): if(use[j] == 0)://是否已经使用 use[j] = 1;//标记 s += origin[j];//给生成串加字符 find(len,j+1,s);//进一步递归 use[j] = 0;//取消标记 |
java完整代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public void result(int k, int i, String s){ if (s.length() == k) { reset[num++] = s; return; } for (int j = i;j < all.size();j++){ if (use[j] != 0)continue; if (use[j] == 0){ use[j] = 1; s += all.get(j); result(k,j+1,s); s = s.substring(0,s.length()-1); use[j] = 0; } } } |