# 回溯算法练习题

78. 子集

1.9K

• 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

• 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

• 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^15
int ** 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 + 3 = 4 。

偷窃到的最高金额 = 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];
}

|
3天前
|

【算法训练-回溯算法 二】【子集组合问题】子集、组合、子集II、组合总和
【算法训练-回溯算法 二】【子集组合问题】子集、组合、子集II、组合总和
42 0
|
3天前
|

【算法训练-回溯算法 一】【排列问题】全排列、全排列II
【算法训练-回溯算法 一】【排列问题】全排列、全排列II
51 0
|
3天前
|

【算法系列篇】递归、搜索和回溯（四）
【算法系列篇】递归、搜索和回溯（四）
63 0
|
3天前
|

7 1
|
3天前
|

8 0
|
3天前
|

18 0
|
3天前
|

23 0
|
3天前
|

【数据结构与算法】递归、回溯、八皇后 一文打尽！
【数据结构与算法】递归、回溯、八皇后 一文打尽！
35 0
|
3天前
|

26 0
|
3天前
|

【算法系列篇】递归、搜索和回溯（三）
【算法系列篇】递归、搜索和回溯（三）
57 0