☆打卡算法☆LeetCode 77、组合 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定两个整数nk，返回范围[1,n]中所有可能的k个数的组合。”

题目链接：

来源：力扣（LeetCode）

链接：77. 组合 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：
输入： n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：
输入： n = 1, k = 1
输出： [[1]]

二、解题

1、思路分析

这道题是求所有的组合，也就是一个问题找出所有的方法，这时候就可以使用回溯算法。

回溯算法是深度优先遍历算法，对于组合问题，排列问题而言，不计较一个组合内元素的顺序性

因此需要按某种顺序展开搜索，才能不遗漏。

2、代码实现

代码参考：

public class Solution {
    public IList<IList<int>> Combine(int n, int k) {
      var res = new List<IList<int>>();
      recruion(1, n, k, new int[k], res);
      return res;
    }

    void recruion(int start, int n, int k, int[] item, IList<IList<int>>res)
    {
      if(k == 0){
          res.Add(item.ToList());
          return;
      }
      for(var i=start;i<=n-k+1;i++){
          item[item.Length - k] = i;
          recruion(i+1, n, k-1, item, res);
      }
    }
}

3、时间复杂度

时间复杂度 ： O(n)

其中n是数组的长度，只需要遍历一遍数组即可求得答案。

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

可以使用深度优先算法解决此问题。利用数组来存储每个符合条件的结果。

因为结果的个数都是k，所以计算下一个结果时不需要清空原有结果数据，否则就变成了回溯算法了。