【算法】从一组数中找出和为指定值的任意组合

2023-07-14 01:55| 来源: 网络整理| 查看: 265

题目：给定的一组整数，给定一个值X，找出和为X的任意组合。

思路：将X视为重量x(kg)的物品，放在天平左侧，数组中的每个数字视为重量为y(kg)的砝码，砝码从大到小逐一放置，直到天平平衡，那么选择的砝码的组合就是我们所要的答案。采用递归的方法。

右侧还有x的余量放置第一个砝码后还有x-y1的余量放置第二个砝码后还有(x-y1)-y2的余量以此类推

static void Main(string[] args) { NumberGame.Execute(); Console.ReadKey(); } public static class NumberGame { private static int[] arr = { 1, 8, 3, 6, 5, 2, 9, 7, 4 }; private const int TOTAL = 11; //指定合计数 private static int groupNum = 0; class NumberType { public int Number { get; set; } public bool Used { get; set; } } public static void Execute() { Console.WriteLine($"数组[{string.Join(",", arr)}]中任意一组数和为{TOTAL}的所有组合:"); List list = arr.OrderBy(x => x).Select(x => new NumberType { Number = x, Used = false }).ToList(); FindNums(list, TOTAL, list.Count - 1); } /// /// 利用递归方法找出所有组合算法：TOTAL按数组倒序逐一减，如有余数remainder>=0则继续递归 /// /// 从小到大排序的数组 /// 剩余数 /// 本次循环次数 private static void FindNums(List list, int remainder, int loop) { if (remainder == 0)//找到一组 { Console.WriteLine($"第{++groupNum}组：{string.Join(" + ", list.Where(x => x.Used).Select(x => x.Number).ToArray())}"); return; } for (int i = loop; i >= 0; i--) { if (!list[i].Used && (remainder - list[i].Number) >= 0) { list[i].Used = true; FindNums(list, remainder - list[i].Number, i - 1); list[i].Used = false; } } } }

【本文地址】

公司简介

联系我们