算法培训课程,算法工程师培训班

算法进修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]]

题解

利用 D F S DFS DFS 算法可解
用 n u m num num 表示当前遍历到的数字初始时 n u m 1 num1 num1。回溯过程中以下两种情况可以直接返回。

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

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

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

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

想法代码

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,i1,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]);        }    }}