公司管理

#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

const int maxn = 30;

int n, a[maxn];

bool ans, used[maxn];

void dfs(int t);

void solve(int s, int e, int c, int aa)
{
	if (aa == 1)
	{
		if (c > 1) dfs(e + 1);
		return;
	}
	for (int i = s; i < e; ++i)
	{
		if (a[i] + 1 > aa) break;
		if (used[i]) continue;
		if (i > 0 && a[i] == a[i - 1] && !used[i - 1]) continue;
		used[i] = true;
		solve(i + 1, e, c + 1, aa - a[i]);
		if (ans) return;
		used[i] = false;
	}
}

void dfs(int t)
{
	if (t >= n) 
	{
		ans = true;
		return;
	}
	solve(0, t, 0, a[t]);
}

int main()
{
	while (scanf("%d", &n) != EOF)
	{
		ans = true;
		for (int i = 0; i < n; ++i)
		{
			scanf("%d", &a[i]);
			if (a[i] < 1)
				ans = false;
		}
		sort(a, a + n);
		if (!ans || a[n - 1] != n) 
		{
			printf("NO\n");
			continue;
		}
		int i = 0;
		for (; i < n; ++i)
			if (a[i] > 1) break;
		if (i < n / 2)
		{
			printf("NO\n");
			continue;
		}
		memset(used, false, sizeof(used));
		ans = false;
		dfs(i);
		if (ans) printf("YES\n");
			else printf("NO\n");
	}
	return 0;	
} 

根据前面这位朋友牛客633068805 的C++版本而来的java版本。（写注释是个好习惯啊）
简单说下我理解的思路：
（1）先用一些值的范围条件过滤一下输入的数，代码注释中的1,2,3，但是3我没想明白为什么（去掉也不影响最终结果）;
（2）对节点从小到大排序，最前面的一定是为1的叶子节点；
（3）从第一个非叶子节点开始，从前面的节点中寻找是否存在它的子节点组合（子节点个数cnt>=2）；

难点：我觉得这题的难点就在于如何回溯，因为这里的回溯不是简单的单层回溯，涉及到两层：
（1）对于单个节点来说，寻找可能的子节点组合会回溯；
（2）对于整个节点数组来说，也涉及到一层回溯：假如前面的节点A找到了第一个满足条件的子节点组合，但是后面遍历到节点B时找不到了，但其实对于节点A除了找到的第一个还有另外的子节点组合，从这个组合遍历下去可达到最终所有都满足。那么如何从B不满足的状态回溯到A可以继续寻找下一个可能满足组合的状态？

解决办法：我称之为“双环递归”(自己瞎取的名字)，我们一般见到的递归都是一个函数，自己调用自己，画个图就是一个环，这里使用了两个函数，dfs可以调用findSum,findSum可以调用调用自身和dfs，画图出来就有两个环。就很好地解决了上面的难点。（这种我也是第一次见，学到了！）

其他细节：
其实findSum就是回溯算法的模板写法，但是这里加了个“树层”去重用来剪枝，如果不加的话会超时。
例子：
[1,1,1,1,3,3,4,8]
找节点4的子节点时，前面第一个3遍历完后不符合，然后遍历到第二个3的时候，前面的3肯定遍历过了，如果相等且used[i-1]=false，说明这个数不能组成有效组合，直接跳过（递归树的同一层去重，这里的作用是剪枝）

ps:关于回溯算法和去重不太熟练的同学可以看这位大佬的题解

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main{
    // 节点是否已经被使用，即是否成为了某个节点的子节点
    static boolean[] used;
    static boolean flag;
    static int n;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            n = sc.nextInt();
            arr = new int[n];
            used = new boolean[n];
            flag = true;
            for(int i=0;i<n;++i){
                arr[i] = sc.nextInt();
                // 1.不能有<1或2存在
                if(arr[i] < 1 || arr[i]==2){
                    flag = false;
                }
            }
            Arrays.sort(arr);
            // 2.最大的一个数必须为n
            if (!flag || arr[n-1]!=n){
                System.out.println("NO");
                continue;
            }
            int idx=0;
            // 找到第一个非叶子节点的下标
            while(idx<n && arr[idx]==1){
                ++idx;
            }
            // 3.第一个非叶子节点的小标idx>=n/2
            if(idx < n/2){
                System.out.println("NO");
                continue;
            }
            flag = false;
            // 4.如果输入满足以上条件，则可能存在这种关系
            dfs(idx);
            if(flag){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }

        }
    }

    // idx为当前遍历节点下标，需要找它的子节点
    public static void dfs(int idx){
        if(idx >= n){
            flag = true;
            return;
        }
        // arr[idx]-1是去掉本身
        findSum(0,idx,0,arr[idx]-1);
    }

    // 从[start,end),未使用的节点节点中寻找是否有和为target的且个数cnt>=2的（因为子节点个数>=2）
    public static void findSum(int start,int end,int cnt,int target){
        if(target == 0){
            // 当前节点找到符合条件的子节点，遍历下一个节点
            if(cnt >= 2){
                dfs(end+1);
            }
            return;
        }

        for(int i=start;i<end && arr[i]<=target;++i){
            if(used[i]){
                continue;
            }
            // 剪枝
            if(i>0 && arr[i]==arr[i-1] && !used[i-1]){
                continue;
            }
            used[i] = true;
            // 回溯
            findSum(i+1,end,cnt+1,target-arr[i]);
            used[i] = false;
        }
    }
}

import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int[] arr = new int[n];
            boolean flag = true;
            int sum = 0;
            for (int i = 0; i < n; i++) {
                arr[i] = scanner.nextInt();
                sum += arr[i];
                if (arr[i] == 2) {
                    flag = false;
                }
            }
            if (!flag) {
                System.out.println("NO");
                continue;
            }
            sum -= n;
            if (sum == n - 1) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

import java.util.Scanner;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            boolean ans = true;
           int n = in.nextInt();
           int[] sort = new int[n];
           for(int i=0;i<n;i++){
                sort[i] = in.nextInt();
            }
            Arrays.sort(sort);
            ArrayList<Integer> list = new ArrayList<>();
            for(int i=0;i<n;i++){
                if(sort[i]==1){
                    list.add(sort[i]);
                }else{
                    ArrayList<Integer> flag = new ArrayList<>();
                    int child = sort[i]-1;
                    int j=list.size()-1;
                     
                    //System.out.println(flag+"flsg");
                    if(!f(list,child,j,flag)){
                       ans = false;
                       break;
                    }
                     
                    for(int k=0;k<flag.size();k++){
                        int location = flag.get(k);
                        list.remove(location);
                        //System.out.println(list+"list");
                    }
                    list.add(sort[i]);
                }
                //System.out.println(list);
            }
            if(!ans){
                System.out.println("NO");
            }else{
                if(list.size()==1){
                    System.out.println("YES");
                }else{
                    System.out.println("NO");
                }
            }
             
                
        }
    }
    public static boolean f(ArrayList<Integer> list,int target,int j,ArrayList<Integer> flag){
        if(j<0){
            if(target!=0){
                return false;
            }else{
                if(flag.size()>=2){
                    return true;
                }
                return false;
            }
        }
        if(list.get(j)==target){
            if(flag.size()>=1){
                flag.add(j);
                return true;
            }
            return f(list,target,j-1,flag);
        }
        if(list.get(j)>target){
            return f(list,target,j-1,flag);
        }
        flag.add(j);
        if(f(list,target-list.get(j),j-1,flag)){
            return true;
        }else{
            flag.remove(new Integer(j));
            return f(list,target,j-1,flag);
        }
    }
}

def dfs(idx,n):
    if(idx >= n):
        used[n] = True
        return
    #arr[idx]-1是去掉本身
    findSum(0,idx,0,ls[idx]-1,n)
def findSum(start,end,cnt,target,n):
    #从[start,end),未使用的节点节点中寻找是否有和为target的且个数cnt>=2的（因为子节点个数>=2）
    if target == 0:
        if cnt >= 2:
            # 当前节点找到符合条件的子节点，遍历下一个节点
            dfs(end+1,n)
    else:
        i=start
        while i < end and ls[i]<=target:
            if used[i]==True:
                i+=1
            # 剪枝,上一个同样值别人不要我也不要
            elif i>0 and ls[i]==ls[i-1] and used[i-1]==False:
                i+=1
            else:
                used[i] = True
                # 回溯，假装没使用这个数
                findSum(i+1,end,cnt+1,target-ls[i],n)
                used[i] = False
                i+=1
while True:
    try:
        n = int(input())
        ls = list(map(int,input().split()))
        ls.sort()
        used = [False] * (n+1)
        if 2 in ls&nbs***bsp;n not in ls:
            print('NO')
            continue
        for idx in range(n):
            if ls[idx]>1:
                break  #找到第一个不为1的数的下标
        dfs(idx,n)
        if used[n]==True:    print('YES')
        else:                print('NO')
    except:break