[416] Partition Equal Subset Sum (TBD)

抄別人的還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);

}