Combinations -- LeetCode - c++编程基础

这道题是NP问题的题目，时间复杂度没办法提高，用到的还是N-Queens中的方法：用一个循环递归处理子问题。实现的代码跟Combination Sum非常类似而且更加简练，因为不用考虑重复元素的情况，而且元素只要到了k个就可以返回一个结果。代码如下：

public ArrayList
  
   > combine(int n, int k) {
    ArrayList
   
    > res = new ArrayList
    
     >(); if(n<=0 || n
     
      (), res); return res; } private void helper(int n, int k, int start, ArrayList
      





        item, ArrayList
       
        > res) { if(item.size()==k) { res.add(new ArrayList
        
         (item)); return; } for(int i=start;i<=n;i++) { item.add(i); helper(n,k,i+1,item,res); item.remove(item.size()-1); } }

NP问题在LeetCode中出现的频率很高，例如N-Queens，Sudoku Solver，Combination Sum等等。不过这类题目都是用一种方法而且也没有办法有时间上的提高，所以还是比较好掌握的。