Add solution for problem 216

BigEgg · BigEgg · commit 19497ea23cd7 · 2020-09-21T18:23:36.000-07:00
diff --git a/LeetCode.Test/0201-0250/0216-CombinationSumIII-Test.cs b/LeetCode.Test/0201-0250/0216-CombinationSumIII-Test.cs
@@ -0,0 +1,64 @@
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+using System.Collections.Generic;
+
+namespace LeetCode.Test
+{
+    [TestClass]
+    public class _0216_CombinationSumIII_Test
+    {
+        [TestMethod]
+        public void CombinationSum3_1()
+        {
+            var solution = new _0216_CombinationSumIII();
+            var result = solution.CombinationSum3(3, 7);
+            AssertHelper.AssertList(new List<IList<int>>()
+            {
+                new int[] { 1, 2, 4},
+            }, result);
+        }
+
+        [TestMethod]
+        public void CombinationSum3_2()
+        {
+            var solution = new _0216_CombinationSumIII();
+            var result = solution.CombinationSum3(3, 9);
+            AssertHelper.AssertList(new List<IList<int>>()
+            {
+                new int[] { 1, 2, 6 },
+                new int[] { 1, 3, 5 },
+                new int[] { 2, 3, 4 },
+            }, result);
+        }
+
+        [TestMethod]
+        public void CombinationSum3_3()
+        {
+            var solution = new _0216_CombinationSumIII();
+            var result = solution.CombinationSum3(4, 1);
+            AssertHelper.AssertList(new List<IList<int>>()
+            {
+            }, result);
+        }
+
+        [TestMethod]
+        public void CombinationSum3_4()
+        {
+            var solution = new _0216_CombinationSumIII();
+            var result = solution.CombinationSum3(3, 2);
+            AssertHelper.AssertList(new List<IList<int>>()
+            {
+            }, result);
+        }
+
+        [TestMethod]
+        public void CombinationSum3_5()
+        {
+            var solution = new _0216_CombinationSumIII();
+            var result = solution.CombinationSum3(9, 45);
+            AssertHelper.AssertList(new List<IList<int>>()
+            {
+                new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
+            }, result);
+        }
+    }
+}
diff --git a/LeetCode.Test/LeetCode.Test.csproj b/LeetCode.Test/LeetCode.Test.csproj
@@ -234,6 +234,7 @@
     <Compile Include="0201-0250\0211-AddAndSearchWordDataStructureDesign-Test.cs" />
     <Compile Include="0201-0250\0212-WordSearchII-Test.cs" />
     <Compile Include="0201-0250\0215-KthLargestElementInAnArray-Test.cs" />
+    <Compile Include="0201-0250\0216-CombinationSumIII-Test.cs" />
     <Compile Include="0201-0250\0217-ContainsDuplicate-Test.cs" />
     <Compile Include="0201-0250\0218-TheSkylineProblem-Test.cs" />
     <Compile Include="0201-0250\0219-ContainsDuplicateII-Test.cs" />
diff --git a/LeetCode/0201-0250/0216-CombinationSumIII.cs b/LeetCode/0201-0250/0216-CombinationSumIII.cs
@@ -0,0 +1,39 @@
+//-----------------------------------------------------------------------------
+// Runtime: 200ms
+// Memory Usage: 25.8 MB
+// Link: https://leetcode.com/submissions/detail/394731091/
+//-----------------------------------------------------------------------------
+
+using System.Collections.Generic;
+using System.Linq;
+
+namespace LeetCode
+{
+    public class _0216_CombinationSumIII
+    {
+        public IList<IList<int>> CombinationSum3(int k, int n)
+        {
+            var results = new List<IList<int>>();
+            Helper(0, k, n, new List<int>(), results);
+            return results;
+        }
+
+        private void Helper(int index, int k, int n, IList<int> current, IList<IList<int>> results)
+        {
+            if (current.Count == k && n == 0)
+            {
+                results.Add(current);
+                return;
+            }
+            if (index >= k || n < 0) return;
+
+            var start = index == 0 ? 1 : current.Last() + 1;
+            for (int i = start; i <= n && i < 10; i++)
+            {
+                var newList = new List<int>(current);
+                newList.Add(i);
+                Helper(index + 1, k, n - i, newList, results);
+            }
+        }
+    }
+}
diff --git a/LeetCode/LeetCode.csproj b/LeetCode/LeetCode.csproj
@@ -225,6 +225,7 @@
     <Compile Include="0201-0250\0211-AddAndSearchWordDataStructureDesign.cs" />
     <Compile Include="0201-0250\0212-WordSearchII.cs" />
     <Compile Include="0201-0250\0215-KthLargestElementInAnArray.cs" />
+    <Compile Include="0201-0250\0216-CombinationSumIII.cs" />
     <Compile Include="0201-0250\0217-ContainsDuplicate.cs" />
     <Compile Include="0201-0250\0218-TheSkylineProblem.cs" />
     <Compile Include="0201-0250\0219-ContainsDuplicateII.cs" />
diff --git a/README.md b/README.md
@@ -1,5 +1,5 @@
 [![AppVeyor Build Status](https://img.shields.io/appveyor/build/bigegg/leetcode-cs?label=Windows%20Build%20Status&logo=AppVeyor&style=flat-square)](https://ci.appveyor.com/project/BigEgg/leetcode-cs)
-[![Solved Problems](https://img.shields.io/badge/Solved%20Problems-811-blue.svg?style=flat-square)](https://github.com/BigEggStudy/LeetCode-CS)
+[![Solved Problems](https://img.shields.io/badge/Solved%20Problems-812-blue.svg?style=flat-square)](https://github.com/BigEggStudy/LeetCode-CS)
 
 # LeetCode
 The C# solutions for LeetCode problems.
@@ -250,6 +250,7 @@ The C# solutions for LeetCode problems.
 | 211 | Add and Search Word - Data structure design | [C#](./LeetCode/0201-0250/0211-AddAndSearchWordDataStructureDesign.cs)(272ms) | O(1) | O(N) | |
 | 212 | Word Search II | [C#](./LeetCode/0201-0250/0212-WordSearchII.cs)(272ms) | O(N*M) | O(K) | |
 | 215 | Kth Largest Element in an Array | [C#](./LeetCode/0201-0250/0215-KthLargestElementInAnArray.cs)(100ms) | O(NLogN) | O(1) | |
+| 216 | Combination Sum III | [C#](./LeetCode/0201-0250/0216-CombinationSumIII.cs)(200ms) | O(9! * K / (9-K)!) | O(K) | |
 | 217 | Contains Duplicate | [C#](./LeetCode/0201-0250/0217-ContainsDuplicate.cs)(112ms) | O(N) | O(N) | |
 | 218 | The Skyline Problem | [C#](./LeetCode/0201-0250/0218-TheSkylineProblem.cs)(288ms) | O(NLogN) | O(N) | |
 | 219 | Contains Duplicate II | [C#](./LeetCode/0201-0250/0219-ContainsDuplicateII.cs)(100ms) | O(N) | O(N) | |
