不知道哪里写得不对【698. 划分为k个相等的子集】

Question

求大神指点迷津,这段代码怎么修改，才可以AC.

例如输入: {4, 3, 2, 3, 5, 2, 1}

5

如果不经过排序，是TRUE，经过排序就是FLASE。 提交的时候把qsort去掉后，卡在了用例

[10,10,10,7,7,7,7,7,7,6,6,6]

3

代码如下：

#define true 1
#define false 0
#define bool int
#define N 17
int vis[N] = {0};
int my_cmp(const void* a, const void* b)
{
    int *pa = (int*)a;
    int *pb = (int*)b;
    return *pa - *pb;
}
int dfs(int* nums, int numsSize, int target, int sum, int box)
{
    int i = 0;
    if (box == 0) {
        return true;
    }
    for (i = 0; i < numsSize ; ++i) {
        if (vis[i] == 0 ) {
            vis[i] = 1;
            if (sum + nums[i] == target && (sum + nums[i] <= target)) {
                return dfs(nums, numsSize, target, 0, box - 1);

            }
            else if (dfs(nums, numsSize, target, sum + nums[i], box)) {
                return true;
            }
            vis[i] = 0;
        }
    }
    return false;
}
bool canPartitionKSubsets(int* nums, int numsSize, int k)
{
    int sum = 0;
    int i, target;
    memset(vis, 0, sizeof(vis));
    for (i = 0; i <numsSize; i++) {
        sum += nums[i];
    }
    if (sum % k != 0) {
        return false;
    }
    target = sum / k;
    return dfs(nums, numsSize, target, 0, k);

}
int main()
{
    int nums[]= {4, 3, 2, 3, 5, 2, 1};
    int res = 0;
    int i;
    qsort(nums, sizeof(nums) / sizeof(int), sizeof(int), my_cmp);
    res = canPartitionKSubsets(nums, sizeof(nums) / sizeof(int), 4);
    printf("%d\n",res);
}

Answer 1

/*
* 算法思想：
* 使用回溯的方法，每次对index位置的数字进行考虑，如果已经分割成功一组，则1.需要从0开始回溯，2. 将k-1；
* k为截至条件，即还剩几组。
* 已经访问的元素，设置为特殊的值SPE，不用另外分配一个数组进行存储了。
* 等回溯返回后，再将其值修改回来
*
**/

#define SPE INT_MAX

bool rec(int *arr, int len, int index,  int target, int target_origin, int k){
    int i;
    int tmp;

    if(k==0) return true;

    if(index>=len) return false;

    for(i=index; i<len; i++) {
        if(arr[i]==SPE || target < arr[i]) continue;

        target -= arr[i];
        tmp = arr[i];
        arr[i] = SPE;

        if(target ==0) {
            target = target_origin;
            if(rec(arr, len,  0, target, target_origin, k-1)) return true;
        }else {
            if(rec(arr, len,  i+1, target, target_origin, k)) return true;
        }

        arr[i] = tmp;
        target += arr[i];
    }

    return false;
}


bool canPartitionKSubsets(int *arr, int len, int k){
    int cnt = 0;
    int i=0;

    for(i=0; i<len; i++) cnt += arr[i];

    if(cnt % k != 0) return false;

    return rec(arr, len, 0 , cnt/k, cnt/k, k) ;
}