Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save jianminchen/eb886960947b4323e0575deb16c4ad09 to your computer and use it in GitHub Desktop.
Save jianminchen/eb886960947b4323e0575deb16c4ad09 to your computer and use it in GitHub Desktop.
Leetcode 40 - combination sum 2- practice with a bug - need to fix the duplicate items in the output
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Leetcode40_CombinationSum
{
class Leetcode40_CombinationSum
{
/* Need to design the algorithm to fix the bug:
*
Input:
[10,1,2,7,6,1,5]
8
Output:
[[1,1,6],[1,2,5],[1,7],[1,2,5],[1,7],[2,6]]
Expected:
[[1,1,6],[1,2,5],[1,7],[2,6]]
*/
static void Main(string[] args)
{
}
public IList<IList<int>> CombinationSum2(int[] numbers, int target)
{
var subsets = new List<IList<int>>();
var subset = new List<int>();
Array.Sort(numbers);
bool[] visited = new bool[numbers.Length];
findSubsetWithSumByUniqueNumbers(subsets, subset, numbers, target, 0, visited);
return subsets;
}
/// <summary>
/// using recursive function to conduct depth first search
/// </summary>
/// <param name="allSubsets"></param>
/// <param name="subset"></param>
/// <param name="numbers"></param>
/// <param name="remaining"></param>
/// <param name="start"></param>
private void findSubsetWithSumByUniqueNumbers(
IList<IList<int>> allSubsets,
IList<int> subset,
int[] numbers,
int remaining,
int start,
bool[] visited)
{
// boundary check - sum value
if (remaining < 0)
{
return;
}
// base case
if (remaining == 0)
{
allSubsets.Add(subset);
return;
}
int length = numbers.Length;
// depth first search using recusive function
// Each number in C may only be used once in the combination.
for (int i = start; i < length; i++)
{
var visit = numbers[i];
var current = i;
var newList = new List<int>(subset);
newList.Add(visit);
var nextUsed = new bool[length];
Array.Copy(visited, nextUsed, length);
nextUsed[i] = true;
var target = remaining - visit;
var nextStart = current + 1; // number can only be used once
findSubsetWithSumByUniqueNumbers(allSubsets, newList, numbers, target, nextStart, nextUsed);
}
}
}
}
@jianminchen
Copy link
Author

Need to design the algorithm to fix the bug:

    Input:
    [10,1,2,7,6,1,5]
    8
    Output:
    [[1,1,6],[1,2,5],[1,7],[1,2,5],[1,7],[2,6]]
    Expected:
    [[1,1,6],[1,2,5],[1,7],[2,6]]

Need to remove duplicate item [1, 2, 5] and [1,7].

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment