[416] Partition Equal Subset Sum

抄別人的還debug 了半天, 天啊我的前途真的很堪慮 ToT

最後, 別人以前可以的code, 現在超過時間了XDDDD

崩潰～～～～～～

void swap(int *a, int *b)

{

    int tmp;

    tmp = *a;

    *a=*b;

    *b= tmp;

    

}

void qqsort(int *nums, int left, int right){

    if (left >= right)

        return;

    int i,j;

    int pivot=nums[left];

    i=left+1;

    j=right;

    while(1)

    {

        while(i<=right && nums[i]<pivot)

            i++;

        while(j>left && nums[j] >= pivot)

            j--;

        if (i>j)

            break;

        swap(&nums[i],&nums[j]);

    }

    swap(&nums[left], &nums[i-1]);

    qqsort(nums,left,i-1);

    qqsort(nums,i+1,right);

}

bool dfs(int target,int curpos, int* nums, int numsSize){

    if (target<0)

        return false;

    if(target==0)

        return true;

    for (int i=curpos;i>=0;i--)

       if (dfs(target-nums[i], (i-1), nums, numsSize)==1)

           return true;

    return false;

}

bool canPartition(int* nums, int numsSize){

    if (numsSize==1)

        return false;

    qqsort(nums,0, numsSize-1);

    int sum=0;

    

    for (int i=0;i<numsSize;i++)

        sum+=nums[i];

    if(sum%2==1)

        return false;

    int target= sum/2;

    if (target < nums[numsSize-1])

        return false;

    return dfs(target, numsSize-1, nums, numsSize);

}

20240609 更新

奇怪～到底為什麼二維改成一維要從後面往前跑！真是看不懂啊啊啊啊啊～～～～（國劇甩頭）

來個我印了log 以後終於比較看的懂的版本 TOT

bool canPartition(int* nums, int numsSize){

int sum = 0;

for(int i = 0; i < numsSize; i++)

sum += nums[i];

if(sum % 2 == 1)

return false;

sum = sum /2;

bool *dp=calloc (sum+1, sizeof(bool));

dp[0] = true;

for(int i = 0; i < numsSize; i++){

for(int j = sum; j >= 0; j--){

printf("%d-%d sum %d , dp:\n", i, nums[i], j);

if(dp[j] && (j + nums[i]) <= sum){

dp[j + nums[i]] = true;

for (int k=0;k<sum+1; k++)

printf(" %d" , dp[k]);

printf("\n");

}

if(dp[sum])

return true;

}

}

return false;

}

至於從sum 往前跑的版本，其實它們印出來的dp 被設成true的過程是一模一樣的 ？！

bool canPartition(int* nums, int numsSize){

int sum = 0;

for(int i = 0; i < numsSize; i++)

sum += nums[i];

if(sum % 2 == 1)

return false;

sum = sum /2;

bool *dp=calloc (sum+1, sizeof(bool));

dp[0] = true;

for (int i=0; i<numsSize;i++)

{

for (int j=sum; j>=nums[i]; j--)

dp[j]= dp[j] || dp[j-nums[i]];

if(dp[sum])

return true;

}

return dp[sum];

}