[编辑1]:-我不知道为什么这个问题被标记为不重点。我正在寻找科学证明该程序的正确性或不正确性。如果您无法回答/没有时间回答,请提供参考资料供进一步阅读,我将不胜感激。
[编辑2]:-问题陈述:-
给出一组正整数S和一个整数K,确定它是否 可以分为三个不相交的子集,每个子集的和 元素为K并覆盖S。
示例:-S:{7,3,2,1,5,4,8},K为10,三个子集为:- {7,3} {5,1} {8,2}
这里是3-way-partition问题的链接。我想出了以下解决方案
using System;
public class Program
{
public static void Main()
{
Console.WriteLine("Hello World");
int[] arr = {7,8};
int sum = 10;
int[] visited = new int[arr.Length];
bool v1 = calc(sum,visited,arr);
bool v2 = calc(sum,arr);
bool v3 = calc(sum,arr);
bool v4 = true;
foreach (var item in visited)
{
if (item == 0)
{
v4 = false;
break;
}
}
Console.WriteLine(v1 && v2 && v3 && v4);
}
public static bool calc(int sum,int[] visited,int[] arr)
{
if (sum < 0)
{
return false;
}
if (sum == 0)
{
return true;
}
else
{
for (int i = 0; i < visited.Length; i++)
{
if (visited[i] == 0)
{
visited[i] = 1;
int[] newV = new int[visited.Length];
// Array.Copy(visited,newV,visited.Length);
if (calc(sum - arr[i],arr) == true)
{
return true;
}
else
{
visited[i] = 0;
}
}
}
return false;
}
}
}
我的方法是使用回溯功能来解决此问题三遍,并检查数组中是否还有未访问的元素。如何证明此算法正确