// https://www.geeksforgeeks.org/combinational-sum/?ref=lbp

// https://www.youtube.com/watch?v=irFtGMLbf-s&ab_channel=GoodTecher

using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        var solution = new Solution();

        var candidates = new int[] {2,3,6,7};

        var target = 7;

        var result = solution.CombinationSum(candidates, target);

        foreach(var item in result){

            Console.WriteLine();

            foreach(var resultListItem in item){

                Console.Write(resultListItem);

            }

        }

    }

}

​

​

public class Solution {

    public IList<IList<int>> CombinationSum(int[] candidates, int target) {

        var  resultList = new List<IList<int>>();

        if (candidates == null || candidates.Length == 0){

            return resultList;

        }

       // step 1: sort array by ASC

       Array.Sort(candidates);

​

        var itemCombination = new List<int>();

        findCombination(resultList, itemCombination, candidates, target, 0);

        return resultList;

    }

    private void findCombination(List<IList<int>> resultList, List<int> itemCombination, int[] candidates, int target, int index){

        if (target == 0){

            resultList.Add(new List<int>(itemCombination));

            return;

        }

        for (int i = index; i < candidates.Length; i++){

            if (candidates[i] > target) {

                break;

            }

            itemCombination.Add(candidates[i]);

            findCombination(resultList, itemCombination, candidates, target - candidates[i], i);

            itemCombination.RemoveAt(itemCombination.Count - 1);

        }

    }

}

​

​

​

​