回溯算法练习题

简介: 回溯算法练习题

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^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:

输入:[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];
}
目录
相关文章
|
3天前
|
存储 算法 程序员
【算法训练-回溯算法 二】【子集组合问题】子集、组合、子集II、组合总和
【算法训练-回溯算法 二】【子集组合问题】子集、组合、子集II、组合总和
42 0
|
3天前
|
机器学习/深度学习 存储 算法
【算法训练-回溯算法 一】【排列问题】全排列、全排列II
【算法训练-回溯算法 一】【排列问题】全排列、全排列II
51 0
|
3天前
|
算法
【算法系列篇】递归、搜索和回溯(四)
【算法系列篇】递归、搜索和回溯(四)
|
3天前
|
算法 决策智能 索引
数据结构与算法 回溯
数据结构与算法 回溯
7 1
|
3天前
|
算法 JavaScript
算法(分治、贪心、dp、回溯、分支限界)总结
算法(分治、贪心、dp、回溯、分支限界)总结
|
3天前
|
算法
算法系列--递归,回溯,剪枝的综合应用(3)(下)
算法系列--递归,回溯,剪枝的综合应用(3)(下)
18 0
|
3天前
|
存储 算法
算法系列--递归,回溯,剪枝的综合应用(3)(上)
算法系列--递归,回溯,剪枝的综合应用(3)(上)
23 0
算法系列--递归,回溯,剪枝的综合应用(3)(上)
|
3天前
|
算法 Java 定位技术
【数据结构与算法】递归、回溯、八皇后 一文打尽!
【数据结构与算法】递归、回溯、八皇后 一文打尽!
|
3天前
|
算法 决策智能
深度探讨回溯算法:追寻解空间的奇妙之旅
深度探讨回溯算法:追寻解空间的奇妙之旅
|
3天前
|
算法
【算法系列篇】递归、搜索和回溯(三)
【算法系列篇】递归、搜索和回溯(三)