工银灵通卡_上海自贸区概念股

给定一个整数数组nums和一个正整数k，找出是否有或许把这个数组分红k个非空子集，其总和都持平。

示例1：输入：nums=[4,3,2,3,5,2,1],k=4输出：True

阐明：有或许将其分红4个子集（5），（1,4），（2,3），（2,3）等于总和。

提示：1<=k<=len(nums)<=16

0<nums[i]<10000

1、动态规划+状况紧缩；时刻复杂度O(n*2^n)，空间复杂度O(2^n)

funccanPartitionKSubsets(nums[]int,kint)bool{\nifk==1{\nreturntrue\n}\nn:=len(nums)\nsort.Ints(nums)\nsum:=0\nfori:=0;i<n;i++{\nsum=sum+nums[i]\n}\nifsum%k!=0{//分不开：false\nreturnfalse\n}\ntarget:=sum/k\nifnums[n-1]>target{//有1个大于平均值：false\nreturnfalse\n}\ntotal:=1<<n\narr:=make([]int,total)\ndp:=make([]bool,total)\ndp[0]=true\nfori:=0;i<total;i++{//枚举状况\nifdp[i]==false{\ncontinue\n}\nforj:=0;j<n;j++{//根据当时状况，增加1个数\nifi&(1<<j)>0{//第j位为1，越过\ncontinue\n}\nnext:=i|(1<<j)//增加完后的值\nifdp[next]==true{\ncontinue\n}\nifarr[i]+nums[j]<=target{\narr[next]=(arr[i]+nums[j])%target\ndp[next]=true\n}else{\nbreak//现已排好序，后面会更大\n}\n}\n}\nreturndp[total-1]\n}

2、回溯；时刻复杂度O(2^n)，空间复杂度O(2^n)

funccanPartitionKSubsets(nums[]int,kint)bool{\nifk==1{\nreturntrue\n}\nn:=len(nums)\nsort.Ints(nums)\nsum:=0\nfori:=0;i<n;i++{\nsum=sum+nums[i]\n}\nifsum%k!=0{//分不开：false\nreturnfalse\n}\ntarget:=sum/k\nifnums[n-1]>target{//有1个大于平均值：false\nreturnfalse\n}\nreturndfs(nums,k,target,0,0,make([]bool,n))\n}\n\nfuncdfs(nums[]int,kint,targetint,indexint,countint,visited[]bool)bool{\nifk==0{\nreturntrue\n}\nifcount==target{\nreturndfs(nums,k-1,target,0,0,visited)//k削减一个，从头开始\n}\nfori:=index;i<len(nums);i++{\nifvisited[i]==true{//nums[i]运用过\ncontinue\n}\nifcount+nums[i]>target{//大于目标值\ncontinue\n}\nvisited[i]=true\ncount=count+nums[i]\nifdfs(nums,k,target,i+1,count,visited)==true{\nreturntrue\n}\ncount=count-nums[i]\nvisited[i]=false\n}\nreturnfalse\n}

3、回溯；时刻复杂度O(2^n)，空间复杂度O(2^n)

funccanPartitionKSubsets(nums[]int,kint)bool{\nifk==1{\nreturntrue\n}\nn:=len(nums)\nsort.Slice(nums,func(i,jint)bool{\nreturnnums[i]>nums[j]\n})\nsum:=0\nfori:=0;i<n;i++{\nsum=sum+nums[i]\n}\nifsum%k!=0{//分不开：false\nreturnfalse\n}\ntarget:=sum/k\nifnums[0]>target{//有1个大于平均值：false\nreturnfalse\n}\nreturndfs(nums,k,target,0,make([]int,k))\n}\n\n//不做剪枝，需求排序从大到小\nfuncdfs(nums[]int,kint,targetint,indexint,sum[]int)bool{\nifindex==len(nums){\nreturntrue\n}\nfori:=0;i<k;i++{\nifsum[i]<target&&sum[i]+nums[index]<=target{\nsum[i]=sum[i]+nums[index]\nifdfs(nums,k,target,index+1,sum)==true{\nreturntrue\n}\nsum[i]=sum[i]-nums[index]\n}\n}\nreturnfalse\n}

Medium标题，能够运用回溯算法，也能够运用动态规划-状况紧缩