回溯算法练习题

78. 子集

中等

1.9K

相关企业

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

void dfs(int* nums, int numsSize, int* returnSize, int* returnColumnSizes,int **ans,int *temp,int tempSize,int begin){for(int i=begin;i<numsSize;i++){temp[tempSize++]=nums[i];ans[*returnSize]=(int*)malloc(sizeof(int)*tempSize);for(int j=0;j<tempSize;j++){ans[*returnSize][j]=temp[j];}returnColumnSizes[*returnSize]=tempSize;(*returnSize)++;dfs(nums,numsSize,returnSize,returnColumnSizes,ans,temp,tempSize,i+1);tempSize--;}return;}
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){int **ans=(int **)malloc(sizeof(int*)*10000);int *temp=(int*)malloc(sizeof(int)*numsSize);*returnColumnSizes=(int*)malloc(sizeof(int)*10000);* returnColumnSizes[0]=0;*returnSize=1;dfs(nums,numsSize,returnSize,*returnColumnSizes,ans,temp,0,0);return ans;
}

90. 子集 II

中等

1K

相关企业

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

int cmp(int* a, int* b) {return *a - *b;
}int *falg[100]={0};
void dfs(int* nums, int numsSize, int* returnSize, int* returnColumnSizes,int **ans,int *temp,int tempSize,int begin){for(int i=begin;i<numsSize;i++){if(i>0&&nums[i-1]==nums[i]&&falg[i-1]==0){continue;}temp[tempSize++]=nums[i];ans[*returnSize]=(int*)malloc(sizeof(int)*tempSize);for(int j=0;j<tempSize;j++){ans[*returnSize][j]=temp[j];}returnColumnSizes[*returnSize]=tempSize;(*returnSize)++;falg[i]=1;dfs(nums,numsSize,returnSize,returnColumnSizes,ans,temp,tempSize,i+1);tempSize--;falg[i]=0;}return;}
int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){int **ans=(int **)malloc(sizeof(int*)*10000);int *temp=(int*)malloc(sizeof(int)*numsSize);qsort(nums, numsSize, sizeof(int), cmp);*returnColumnSizes=(int*)malloc(sizeof(int)*10000);* returnColumnSizes[0]=0;*returnSize=1;dfs(nums,numsSize,returnSize,*returnColumnSizes,ans,temp,0,0);return ans;
}

491. 递增子序列

中等

592

相关企业

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

提示：

• 1 <= nums.length <= 15
• -100 <= nums[i] <= 100

void backTrack(int* nums, int numsSize, int* returnSize, int** returnColumnSizes, int** returnNums,int *stack,int top, int index)
{if (index > numsSize){return;}if (top >= 2){returnNums[*returnSize] = (int*)malloc(sizeof(int) * top);memcpy(returnNums[*returnSize], stack,sizeof(int) * top);(*returnColumnSizes)[*returnSize] = top;*returnSize = *returnSize + 1;}int i = index + 1;bool  hashSet[201] = { 0 };    //去重for (; i < numsSize; i++){if (nums[i] >= nums[index] ){if (hashSet[nums[i] + 100] == 0){hashSet[nums[i] + 100] = 1;stack[top] = nums[i];backTrack(nums, numsSize, returnSize, returnColumnSizes, returnNums, stack, top + 1, i);}}}}int** findSubsequences(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) 
{*returnSize = 0;*returnColumnSizes = (int*)     malloc(sizeof(int)*  32768);    //2^15int ** returnNums  = (int**)    malloc(sizeof(int*)* 32768);(*returnColumnSizes)[0] = 0;returnNums[0]           = NULL;if (numsSize == 1){   return returnNums;}//用到栈int* stack = (int*)malloc(sizeof(int) * numsSize);int i = 0;int  hashSet[201] = { 0 };    //去重for (i = 0; i < numsSize; i++){if(hashSet[nums[i] + 100] == 0){hashSet[nums[i] + 100] = 1;stack[0] = nums[i];backTrack(nums, numsSize, returnSize, returnColumnSizes, returnNums, stack, 1, i);}}return returnNums;
}

198. 打家劫舍

中等

2.4K

相关企业

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

通过次数

693.1K

提交次数

1.3M

通过率

54.2%

int rob(int* nums, int n){int dp[n+2];memset(dp,0,sizeof(dp));for(int i=0;i<n;i++) dp[i+2]=fmax(dp[i+1],dp[i]+nums[i]);return dp[n+1];
}