所谓排列，是指从给定的元素序列中依次取出元素，需要考虑取出顺序。比如，取出元素3, 5，因取出顺序的不同，则形成的序列{3, 5}与{5, 3}是不同的排列序列。对于长度为n的元素序列取出k个元素，则共有A(n, k)种取法。所谓组合，也是从元素序列中依次取出元素，与排列不同的是不需要考虑取出顺序；因此其取法数为C(n, k)。

LeetCode有两个问题分属于组合、排列： 与 。

组合

要求给出对于序列1~n 的取出k个元素的各种取法。采用DFS模拟组合时，可看做节点i与节点j(j = i+1, … , n)都相连接，然后DFS遍历整张有向图，代码实现如下：

public List
    
     
      > combine(int n, int k) {    List
      
       
        > result = new ArrayList<>();    if (n <= 0 || n < k) {        return result;    }    List
        
          tmp = new ArrayList<>();    dfs(n, k, 1, tmp, result);    return result;}// DFS for combinationprivate void dfs(int n, int k, int start,                 List
         
           tmp, List
          
           
            > result) { if (tmp.size() == k) { result.add(new ArrayList
            
             (tmp)); return; } for (int i = start; i <= n; i++) { tmp.add(i); dfs(n, k, i + 1, tmp, result); tmp.remove(tmp.size() - 1); // remove the last }}
            
           
          
         
        
       
      
     
    

排列

DFS实现排列与组合相类似，唯一不同之处在于，节点i与其他所有节点都连接。因此，所构造的图是一个完全连通图。DFS实现排列如下：

public List
    
     
      > permute(int[] nums) {    List
      
       
        > result = new ArrayList<>();    if (nums.length == 0) {        return result;    }    List
        
          tmp = new ArrayList<>();    dfs(nums, tmp, result);    return result;}// DFS for permutationprivate void dfs(int[] nums, List
         
           tmp, List
          
           
            > result) { int n = nums.length; if (tmp.size() == n) { result.add(new ArrayList<>(tmp)); return; } for (int i = 0; i < n; i++) { // nums[i] has not been visited if (!tmp.contains(nums[i])) { tmp.add(nums[i]); dfs(nums, tmp, result); tmp.remove(tmp.size() - 1); } }}
           
          
         
        
       
      
     
    

上述代码中，可以用一个visit数组来标记节点是否被访问，这样优化将contains的时间复杂度从\(O(n)\)优化到\(O(1)\)。