Find out all unique combinations of sum of a Number N in C#

In this article, we will see how to find the unique combination of the sum from the given number in C#.

1. Combination Sum – Problem Statement

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to the target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to the target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1 Output: []

Example 4:

Input: candidates = [1], target = 1 Output: [[1]]

Example 5:

Input: candidates = [1], target = 2 Output: [[1,1]]

C# Code:

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication1
{
    public class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Please give number to get sum");
            int num = Convert.ToInt16(Console.ReadLine());
            UniqueNumberTobeSum(num);
        }

        public static void UniqueNumberTobeSum(int num)
        {
            int[] array = new int[num + 1];
            for (int i = 1; i <= num; i++)
            {
                array[i] = i;
            }
            List<int> currentList = new List<int>();
            List<List<int>> output = new List<List<int>>();
            UniqueCombinationSum(array, num, 0, 1, currentList, output);
            Console.WriteLine("unique combinations of sum of a Number ");
            foreach (var item in output)
            {
                StringBuilder s = new StringBuilder();
                foreach (var item1 in item)
                {
                    s.Append(item1.ToString());
                }

               
                Console.WriteLine(s);
                s = null;
            }
        }
        private static void UniqueCombinationSum(int[] array, int target, int sum, int index, List<int> currentList, List<List<int>> output)
        {
            if (sum == target)
            {
                List<int> newList = new List<int>();
                newList.AddRange(currentList);
                output.Add(newList);
                return;
            }
            else if (sum > target)
            {
                return;
            }
            else
            {
                for (int i = index; i < array.Length; i++)
                {
                    currentList.Add(array[i]);
                    UniqueCombinationSum(array, target, sum + array[i], i + 1, currentList, output);
                    currentList.Remove(array[i]);
                }
            }
        }

    }


}

Output: