Given two integers n and k , 
return all possible combinations of k numbers out of 1 ... n . 
Forexample,If n=4 and k=2 ,asolutionis:
 [ [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

solution1

此方法超时

  class Solution(object):
      def combine(self, n, k):
          """
          :type n: int
          :type k: int
          :rtype: List[List[int]]
          """
          res = []
          n_list = [i for i in range(1, n+1)]
          self.backtracking(res, n_list, k, [])
          return res

      def backtracking(self, res, n_list, target, sublist):
          if len(sublist) > target:
              return

          if len(sublist) == target and sublist not in res:
              res.append(sublist)
              return

          for item in n_list:
              if item in sublist:
                  continue
              if sublist and item < sublist[-1]:
                  continue
              tmp_n_list = n_list[:]
              tmp_n_list.remove(item)
              self.backtracking(res, tmp_n_list, target, sublist+[item])        
  class Solution {
  public:
    vector<vector<int>> combine(int n, int k) {
      vector<vector<int>> result;
      vector<int> path;

      dfs(n, k, 1, 0, path, result);

      return result;
    }
  private:
    // start 开始的数 cur 已经选择的数目
    static void dfs(int n, int k, int start, int cur, vector<int> &path, vector<vector<int>> &result) {
      if (cur==k) {
        result.push_back(path);
      }

      for (int i=start; i<n; ++i) {
        path.push_back(i);
        dfs(n, k, i+1, cur+1, path, result);
        path.pop_back();
      }
    }
  };

优化上述方法

可以优化的点是: -

  class Solution(object):
      def combine(self, n, k):
          """
          :type n: int
          :type k: int
          :rtype: List[List[int]]
          """
          res = []
          self.backtracking(res, n, k, [], 0)
          return res

      def backtracking(self, res, n, target, sublist, start):
          if len(sublist) > target:
              return

          if len(sublist) == target:
              res.append(sublist[:])
              return

          for item in range(start, n):

              sublist.append(item+1)
              self.backtracking(res, n, target, sublist, item+1)
              sublist.pop(-1)
class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        终于找到问题所在了,本质上是深拷贝和浅拷贝的问题;
        intermediate[:]会新建一个对象,地址也是不同的
        而如果用的是intermediate的话,result这个append操作,添加进去的其实都是相同的对象啦。

        """
        d = []
        def combineDFS(n, start, intermediate, k, result):
            if k == 0:
                result.append(intermediate[:])
                return
            for i in xrange(start, n):
                intermediate.append(i+1)
                combineDFS(n, i+1, intermediate, k-1, result)
                intermediate.pop()


        result = []
        combineDFS(n, 0, [], k, result)

        return result
# 这个方法没有超时,关键点是引入了遍历开始的参数,基于上次的结果,每次进行
# 下一步迭代的时候,都可以进行对过去已经操作过的删除掉
# 整体的负责度是O(n!)

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        res = []
        self.backtracking(res, n, k, [], 0)
        return res

    def backtracking(self, res, n, target, sublist, start):
        if len(sublist) > target:
            return

        if len(sublist) == target:
            res.append(sublist[:])
            return

        for item in range(start, n):

            sublist.append(item+1)
            self.backtracking(res, n, target, sublist, item+1)
            sublist.pop(-1)