算法进修Day-38

算法进修Day-38

77. 组合

难度：中等
题目要求：
给定两个整数 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]]

题解

利用 $DFS$ 算法可解
用 $num$ 表示当前遍历到的数字，初始时 $num=1$。回溯过程中，以下两种情况可以直接返回。

• 如果当前组合中有 $k$ 个数，则得到一个 $k$ 个数的组合，将其添加到答案中，不需要继续遍历更多的数字。

• 如果当前组合中的数字过少，即使将 $[num,n]$ 范围中的所有整数都加入当前组合都无法使组合中的数字个数达到 $k$，则在当前组合的情况下一定不可能得到 $k$ 个数的组合。

其余情况下，对于当前遍历到的数字 $num$，分别考虑将其加入组合与不加入组合两种情况，并执行回溯。

使用剪枝的情况下，可以排除不可能的组合，需要遍历的组合数从 $2^n$ 减少到 $C_n^k$

想法代码

class Solution
{public static void Main(String[] args){Solution solution = new Solution();int n = 4;int k = 2;IList<IList<int>> res = solution.Combine(n, k);foreach (var i in res){foreach (var j in i){Console.Write(j + " ");}Console.WriteLine();}}public IList<IList<int>> Combine(int n, int k){IList<IList<int>> res = new List<IList<int>>();List<int> list = new List<int>();if (n < k || k <= 0){return(IList<IList<int>>)(list);}DFS(n, k, 1, list, res);return res;}public void DFS(int n, int k, int begin, IList<int> list, IList<IList<int>> res){IList<int> path = new List<int>();if (list.Count == k){for (int i = 0; i < list.Count; i++){path.Add(list[i]);}res.Add(path);return;}for (int i = begin; i <= n; i++){list.Add(i);DFS(n,k,i+1,list,res);list.RemoveAt(list.Count-1);}}
}

78. 子集

难度：中等
题目要求
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例1

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例2

输入：nums = [0]
输出：[[],[0]]

题解

利用回溯算法可解
每个结果都需要存储，不需要约束条件
由于每个都需要存储，所以不需要剪枝
注意，这个算法依旧需要回头

想法代码

public class Solution
{public static void Main(string[] args){Solution solution = new Solution();int[] nums = { 1, 2, 3 };IList<IList<int>> res = solution.Subsets(nums);foreach (var i in res){foreach (var j in i){Console.Write(j + " ");}Console.WriteLine();}}public IList<IList<int>> Subsets(int[] nums){IList<IList<int>> ans = new List<IList<int>>();if (nums == null || nums.Length == 0){return ans;}DFS(nums, new List<int>(), 0, ans);return ans;}public void DFS(int[] nums, List<int> path, int start,IList<IList<int>> ans){ans.Add(new List<int>(path));for (int i = start; i < nums.Length; i++){path.Add(nums[i]);DFS(nums, path, i + 1,ans);path.Remove(nums[i]);}}
}