LeetCode Online Judge 题目C# 练习 - Combination Sum

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]

 1 public static List<List<int>> CominationSum(int[] candidates, int target)
 2         {
 3             Dictionary<int, List<List<int>>> map = new Dictionary<int, List<List<int>>>();
 4             //Array.Sort(candidates);
 5 
 6             for (int cur_sum = 1; cur_sum <= target; cur_sum++)
 7             {
 8                 for (int cand_index = 0; cand_index < candidates.Length; cand_index++)
 9                 {
10                     if (cur_sum < candidates[cand_index])
11                         continue;
12                     if (cur_sum == candidates[cand_index])
13                     {
14                         List<int> templist = new List<int> { candidates[cand_index] };
15                         if (map.ContainsKey(cur_sum))
16                             map[cur_sum].Add(templist);
17                         else
18                         {
19                             List<List<int>> templistlist = new List<List<int>>();
20                             templistlist.Add(templist);
21                             map.Add(cur_sum, templistlist);
22                         }
23                         continue;
24                     }
25 
26                     int pre_cur_sum = cur_sum - candidates[cand_index];
27                     if (!map.ContainsKey(pre_cur_sum))
28                         continue;
29                     else
30                     {
31                         int pre_cur_sum_size = map[pre_cur_sum].Count;
32                         for (int i = 0; i < pre_cur_sum_size; i++)
33                         {
34                             if (map[pre_cur_sum][i][map[pre_cur_sum][i].Count - 1] <= candidates[cand_index])
35                             {
36                                 List<int> templist = new List<int>(map[pre_cur_sum][i]);
37                                 templist.Add(candidates[cand_index]);
38                                 if (map.ContainsKey(cur_sum))
39                                     map[cur_sum].Add(templist);
40                                 else
41                                 {
42                                     List<List<int>> templistlist = new List<List<int>>();
43                                     templistlist.Add(templist);
44                                     map.Add(cur_sum, templistlist);
45                                 }
46                             }
47                         }
48                     }
49                 }
50             }
51 
52             return map[target];
53         }

代码分析：

　　这题也是使用DP的思想，k(7) = k(7-arr[i]) + arr[i];

　　按题目的例子：candidate set 2,3,6,7 and target 7。

　　target = 1 : 返回null。

　　target = 2 : 返回 {2},

　　target = 3 : 返回 target - 2 = null, {3}

　　target = 4 : 返回 target - 2 = {2} + {2} = {2, 2}, target - 3 = null,

　　tatget = 5 : 返回 target - 2 = 因为 3 > 2 不插入到list中（因为题目要求a1 ≤ a2 ≤ … ≤ ak）

　　　　　　　　 返回 target - 3 = {2} + {3} = {2, 3}

　　target = 6 : 返回 target - 2 = {2, 2} + {2} = {2, 2, 2}

　　　　　　　　 返回 target - 3 = {3} + {3} = {3, 3}

　　　　　　　　 返回 {6}

　　target = 7 : 返回 target - 2 = {2, 3} + {2}, 3 > 2 不返回

　　　　　　　　 返回 target - 3 = {2, 2} + {3 } = {2, 2, 3}

　　　　　　　　 返回 target - 6 = null

　　　　　　　　 返回 {7}

　　所以答案是 {2,2,3}, {7}。上面解释的时候用的动词可能不太正确。但是基本思路还是清楚的吧。