靜夜的部落格

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

Each number in C may only be used once in the combination.

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 10,1,2,7,6,1,5 and target 8, 
A solution set is: 
[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6] 

個人解

private List<List<int>> CS(int[] ListGroup, int target)
{
List<int> mListGroup = new List<int>();
Array.Sort(ListGroup);

List<string> mAns = new List<string>();
List<List<int>> Rtn = new List<List<int>>();

for (int i = 0; i < ListGroup.Length; i++)
{
mListGroup.Add(ListGroup[i]);
}

foreach (List<int> A1 in Check1(mListGroup, target))
{
if (A1.Count > 0)
{
int[] aa = new int[A1.Count];
string tmpAns = "";

for (int i = 0; i < A1.Count; i++)
{
aa[i] = A1[i];
}

Array.Sort(aa);

for (int i = 0; i < A1.Count; i++)
{
if (!string.IsNullOrEmpty(tmpAns))
{
tmpAns += ", ";
}
tmpAns += aa[i].ToString();
}

if (mAns.IndexOf(tmpAns) < 0)
{
mAns.Add(tmpAns);
Rtn.Add(A1);
}
}
}
return Rtn;
}

//
private List<List<int>> Check1(List<int> List, int target)
{
List<int> TempAns = new List<int>();

List<List<int>> AnsList = new List<List<int>>();

for (int i = 0; i < List.Count; i++)
{
//確認
if (List[i] == target)
{
TempAns = new List<int>();
TempAns.Add(List[i]);

AnsList.Add(TempAns);
}

//補差異
if (List[i] < target)
{
List<int> mList = new List<int>();

for (int j = 0; j < List.Count; j++)
{
if (j != i)
{
mList.Add(List[j]);
}
}

foreach (List<int> L1 in Check1(mList, target - List[i]))
{
if (L1.Count > 0)
{
TempAns = new List<int>();

TempAns.Add(List[i]);

foreach (int L2 in L1)
{
TempAns.Add(L2);
}

AnsList.Add(TempAns);
}
}
}
}
return AnsList;
}