自己网站页面设计软件,口碑营销案例2021,西安保洁公司网站建设,上海网站制作网站制作公司给你一个整数数组 nums #xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集#xff08;幂集#xff09;。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
思路一#xff1a;回溯
void backtracking(int* nums, int numsSize, int** res, int* ret…给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
思路一回溯
void backtracking(int* nums, int numsSize, int** res, int* returnSize, int** returnColumnSizes, int* path, int pathSize, int startIndex) {res[*returnSize] (int*)malloc(sizeof(int) * pathSize);memcpy(res[*returnSize], path, sizeof(int) * pathSize);(*returnColumnSizes)[*returnSize] pathSize;(*returnSize);for (int i startIndex; i numsSize; i) {path[pathSize] nums[i];backtracking(nums, numsSize, res, returnSize, returnColumnSizes, path, pathSize 1, i 1);}
}int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {*returnSize 0;*returnColumnSizes (int*)malloc(sizeof(int) * 10001);int** res (int**)malloc(sizeof(int*) * 10001);int* path (int*)malloc(sizeof(int) * numsSize);backtracking(nums, numsSize, res, returnSize, returnColumnSizes, path, 0, 0);return res;
}
分析
本题与上一题相似利用回溯算法将数组内子集全部列出即可path[pathSize] nums[i];
backtracking(nums, numsSize, res, returnSize, returnColumnSizes, path, pathSize 1, i 1);将子集全部列出最后返回res
总结
本题考察回溯的应用将子集按顺序全部列出即可解决
