等和划分

回溯

class Solution {
    boolean flag=false;
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if(sum%2!=0){
            return false;
        }
        boolean[] vis=new boolean[nums.length];
        dfs(nums,0,sum/2,vis);
        return flag;

    }
    public void dfs(int[] nums,int cur,int target,boolean[] vis){
        if(cur==target||flag){
            flag=true;
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(!vis[i]){
                cur+=nums[i];
                vis[i]=true;
                dfs(nums,cur,target,vis);
                cur-=nums[i];
                vis[i]=false;
            }
        }

    }
}

dp

dp[i][j]表示前i个元素是否存在和为j

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;int maxv=Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            maxv=Math.max(maxv,nums[i]);
        }
        if(sum%2!=0){
            return false;
        }
        if(maxv>sum/2){
            return false;
        }
        int target=sum/2;
        int n=nums.length;
        boolean[][] dp=new boolean[n][target+1];
        for(int i=0;i<n;i++){
            dp[i][0]=true;
        }
        dp[0][nums[0]]=true;
        for(int i=1;i<n;i++){
            for(int j=0;j<target+1;j++){
                if(nums[i]>j){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=dp[i-1][j-nums[i]]|dp[i-1][j];   
                }
            }
        }
        return dp[n-1][target];
    }
}

数组的均值分割

数组均值分割

class Solution {
    public boolean splitArraySameAverage(int[] nums) {
        int n=nums.length;
        if(n==1){
            return false;
        }
        int sum = Arrays.stream(nums).sum();
        for(int i=0;i<n;i++){
            nums[i]=nums[i]*n-sum;
        }
        int m=n/2;
        dfs1(m,n,0,nums);//将右半部分
        int left=0;int right=0;
        for(int i=m;i<n;i++){
            right+=nums[i];
        }
        if(map.containsKey(left)){
            map.put(left,map.getOrDefault(left,0)-1);
            if(map.get(left)==0){
                map.remove(left);
            }
        }
        if(map.containsKey(0)){
            return true;
        }
        map.put(left,map.getOrDefault(left,0)+1);
        if(map.containsKey(right)){
            map.put(right,map.getOrDefault(right,0)-1);
            map.remove(right);
        }
        //计算左边的和
        int left_sum=0;
        for(int i=0;i<m;i++){
            left_sum+=nums[i];
        }
        if(map.containsKey(-left_sum)){
            return true;
        }
        return dfs2(0,m,0,0,nums);
    }


    Map<Integer,Integer> map=new HashMap<>();
    public void dfs1(int start,int n,int sum,int[] nums){
        if(start==n){
            map.put(sum,map.getOrDefault(sum,0)+1);
        }else{
            dfs1(start+1,n,sum,nums);
            dfs1(start+1,n,sum+nums[start],nums);
        }
    }

    public boolean dfs2(int start,int n,int sum,int cnt,int[] nums){
        if(start==n){
            if(cnt>0&&cnt<n&&map.containsKey(-sum)){
                return true;
            }
            return false;
        }else{
            if (dfs2(start + 1, n, sum, cnt,nums)) {
                return true;
            }
            if(dfs2(start+1,n,sum+nums[start],cnt+1,nums)){
                return true;
            }
            return false;
        }
    }
}