算法题求解

来源于EPIC的OA，具体是列出Permutation(n,m)(n is not equal to m)的所有情况。在网上找了很长时间代码，找到了列出所有combination(n,m) 和 Permutation(n,n)的代码，没找到列Permutation(n,m)的，所以就把这两个组合起来先求combination再对每个combination用permutation。但想想这肯定不是最简单的解法，有大神知道怎么可以一部做出来吗?

好难，真的好难

1. public class Permutations {
   
2.     public ArrayList<ArrayList<Integer>> permute(int[] num, int m) {
   
3.         ArrayList<ArrayList<Integer>> permutations = new ArrayList<ArrayList<Integer>>();
   
4.         if (num != null && m <= num.length) {
   
5.             dfs(num, permutations, new ArrayList<Integer>(), new boolean[num.length], m);
   
6.         }
   
7.         return permutations;
   
8.     }
   
9. 
   
10. 
    
11.     private void dfs(int[] num, ArrayList<ArrayList<Integer>> permutations, ArrayList<Integer> permutation, boolean[] used, int m) {
    
12.         if (m == permutation.size()) {
    
13.             permutations.add(new ArrayList<Integer>(permutation));
    
14.             return;
    
15.         }
    
16. 
    
17.         for (int i = 0; i < used.length; ++i) {
    
18.             if (!used[i]) {
    
19.                 used[i] = true;
    
20.                 permutation.add(num[i]);
    
21.                 dfs(num, permutations, permutation, used, m);
    
22.                 permutation.remove(permutation.size() - 1);
    
23.                 used[i] = false;
    
24.             }
    
25.         }
    
26.     }
    
27. }

复制代码

回溯法。。。

试试递归？