前言
组合运算是一个数据概念，具体来说，组合运算就是从给定元素集合中选择特定数量的元素进行运算，而不考虑元素的顺序，关注的是哪些元素被选中，而不关心它们的排列顺序。
比如，有一个整数数组 int[] numbers = { 1, 2, 3}，它的所有组合就是：
1 2 3 1,2 1,3 2,3 1,2,3
简单例子：列出一个整数数组 int[] numbers = { 1, 2, 3, 4 } 的所有组合
using System; using System.Collections.Generic; class Program { static void Main() { int[] numbers = { 1, 2, 3, 4 }; List<List<int>> combinations = GenerateCombinations(numbers); foreach (var combination in combinations) { Console.WriteLine(string.Join(", ", combination)); } } static List<List<int>> GenerateCombinations(int[] numbers) { List<List<int>> result = new List<List<int>>(); for (int i = 1; i <= numbers.Length; i++) { GenerateCombinationsUtil(numbers, i, 0, new List<int>(), result); } return result; } static void GenerateCombinationsUtil(int[] numbers, int k, int start, List<int> currentCombination, List<List<int>> result) { if (k == 0) { result.Add(new List<int>(currentCombination)); return; } for (int i = start; i < numbers.Length; i++) { currentCombination.Add(numbers[i]); GenerateCombinationsUtil(numbers, k - 1, i + 1, currentCombination, result); currentCombination.RemoveAt(currentCombination.Count - 1); } } }
运行后以上代码会生成整数数组 { 1, 2, 3, 4 } 的所有可能组合，并将这些组合打印到控制台。
进阶一：根据需要打印出数组的组合
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int[] numbers = { 1, 2, 3, 4 }; int k = 2; // 选择的元素数量 List<List<int>> combinations = GenerateCombinations(numbers, k); foreach (var combination in combinations) { Console.WriteLine(string.Join(", ", combination)); } } static List<List<int>> GenerateCombinations(int[] numbers, int k) { List<List<int>> result = new List<List<int>>(); List<int> currentCombination = new List<int>(); GenerateCombinationsHelper(numbers, k, 0, 0, currentCombination, result); return result; } static void GenerateCombinationsHelper(int[] numbers, int k, int start, int currentSize, List<int> currentCombination, List<List<int>> result) { if (currentSize == k) { result.Add(new List<int>(currentCombination)); return; } for (int i = start; i < numbers.Length; i++) { currentCombination.Add(numbers[i]); GenerateCombinationsHelper(numbers, k, i + 1, currentSize + 1, currentCombination, result); currentCombination.RemoveAt(currentCombination.Count - 1); } } }
进阶二：排列出集合的组合，所进行运算
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { // 创建集合 List<Item> itemsList = new List<Item> { new Item { Number = 1, Amount = 100 }, new Item { Number = 2, Amount = 200 }, new Item { Number = 3, Amount = 300 } }; // 进行组合 List<List<Item>> combinations = GenerateCombinations(itemsList); // 对组合结果进行运算 StringBuilder sb = new StringBuilder(1024); foreach (var combination in combinations) { for (var i = 0; i < combination.Count; i++) { var item = combination[i]; sb.Append(item.Number); if (i < combination.Count - 1) { sb.Append(" + "); } } var cash = combination.Sum(x => x.Amount); sb.AppendLine($" = {cash}"); } // 打印结果 Console.WriteLine(sb.ToString()); } static List<List<Item>> GenerateCombinations(List<Item> numbers) { List<List<Item>> result = new List<List<Item>>(); // 从 2 个元素开始进行组合 for (int i=2; i <= numbers.Count; i++) { GenerateCombinationsHelper(numbers, i, 0, new List<Item>(), result); } return result; } static GenerateCombinationsHelper(List<Item> numbers, int k, int start, List<Item> currentCombination, List<List<Item>> result) { if (k == 0) { result.Add(new List<Item>(currentCombination)); return; } for (int i = start; i < numbers.Count; i++) { currentCombination.Add(numbers[i]); GenerateCombinationsHelper(numbers, k - 1, i + 1, currentCombination, result); currentCombination.RemoveAt(currentCombination.Count - 1); } } } // 定义集合元素类 class Item { // 编号 public int Number { get; set; } // 金额 public decimal Amount { get; set; } }
总结
组合运算是面试中经常被问到的一个算法题，在实际业务中也会经常使用，希望以上例子对你有所帮助。
我是老杨，一个奋斗在一线的资深研发老鸟，让我们一起聊聊技术，聊聊人生。
都看到这了，求个点赞、关注、在看三连呗，感谢支持。
