I got the following interview question:

Using the following function signature, write a C# function that prints out every combination of indices using Console.WriteLine() whose values add up to a specified sum, n. Values of 0 should be ignored.

public void PrintSumCombinations(List<int> numbers, int n);

·         It’s okay to use additional private functions to implement the public function

·         Be sure to print out the indices of numbers and not the values at those indices

·         Don’t worry too much about memory or CPU optimization; focus on correctness

To help clarify the problem, calling the function with the following input:

List<int> numbers = new List<int> { 1, 1, 2, 2, 4 };

PrintSumCombinations(numbers, 4);

Should result in the following console output (the ordering of the different lines isn’t important and may vary by implementation):

0 1 2 (i.e. numbers[0] + numbers[1] + numbers[2] = 1 + 1 + 2 = 4)

0 1 3

2 3

4

Here is my hint: Generate the variations based on permutations  and regardless of the content, then check each sequence for the expected sum.
public void Permute(ref List<int> numbers, ref List<int> candidate, ref bool[] used, int n)



{

  if (candidate.Sum() == n)



{
  candidate.ForEach(x => Console.Write(x.ToString() + " "));

Console.WriteLine();



}

for (int i = 0; i < numbers.Count; i++)



{
  if (used[i]) continue;



candidate.Add(numbers[i]);
  used[i] = true;

Permute(ref numbers, ref candidate, ref used, n);



candidate.Remove(candidate.Last());
  used[i] = false;



}

} 

For combinations, we could take different length substrings and permute them. There may be repetitions but we process just the same.

And here is another way to solve the problem
public static void Combine(ref List<IndexedNumber> numbers, ref List<IndexedNumber> candidate, ref List<List<IndexedNumber>> sequences, int level, int start, int n)



{
  for (int i = start; i < numbers.Count; i++)



{
  if (candidate.Contains(numbers[i]) == false)



{

candidate[level] = numbers[i];
  if (candidate.Sum() == n)

sequences.Add(new List<IndexedNumber>(candidate));

if (i < numbers.Count - 1)

Combine(ref numbers, ref candidate, ref sequences, level + 1, start + 1, n);

candidate[level] = new IndexedNumber() { Number = 0, Index = -1 };



}

}

}