Skip to content

39 Combination Sum ✅

Problem

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.
  • For example, given candidate set 2,3,6,7 and target 7, A solution set is:
  [
    [7],
    [2, 2, 3]
  ]

Thoughts

Idea is to use a modified DFS.

alt

alt

C# Solution

using System;
using System.Collections.Generic;

namespace Algorithms.Medium
{
  public class CombinationSum
  {
    public static List<List<int>> Get(List<int> list, int target)
    {
      var ans = new List<List<int>>();
      // Might need to sort input if not sorted
      DFS(list, target, ans, new List<int>(), 0);

      return ans;
    }

    private static void DFS(List<int> list, int target, List<List<int>> ans, List<int> curr, int startIndex)
    {
      if (target == 0)
      {
        ans.Add(new List<int>(curr));
        return;
      }

      for (var i = startIndex; i < list.Count; i++)
      {
        if (list[i] > target) break;

        curr.Add(list[i]);
        DFS(list, target - list[i], ans, curr, i);

        curr.RemoveAt(curr.Count - 1);
      }
    }
  }
}

C# Tests

using System.Collections.Generic;
using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class CombinationSumTests
  {
    [Fact]
    public void TestName()
    {
      Assert.Equal(new List<List<int>> {
        new List<int> {2, 2, 3},
        new List<int> {7}
        }, CombinationSum.Get(new List<int> { 2, 3, 6, 7 }, 7));
    }
  }
}

Follow-up: what if the given set contains duplicates? 40. Combination Sum II

```cs{2} for (var i = startIndex; i < list.Count; i++) { if (i > startIndex && list[i] == list[i-1]) continue;

    curr.Add(list[i]);
    DFS(list, target - list[i], ans, curr, i);

    curr.RemoveAt(curr.Count - 1);
  }

```

Follow-up

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. CombinationSum.Get(int k, int n); cs{3} private static void DFS(List<int> list, int target, List<List<int>> ans, List<int> curr, int startIndex) { if (target == 0 && curr.Count == k) { ans.Add(new List<int>(curr)); return; } for (var i = startIndex; i < list.Count; i++) { if (list[i] > target) break; // No need to go further curr.Add(list[i]); DFS(list, target - list[i], ans, curr, i); curr.RemoveAt(curr.Count - 1); } }

Article references