暴力模拟
$O(N³)$
菜狗代码,仅供参考,不建议模仿
import java.io.*;
import java.util.*;
public class Main {
// static Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
static final int N = 110;
static final int M = (int) 1e5+5;
static int n;
static int[] nums = new int[N];
static boolean[][] memo=new boolean[N][M];
static Set<Integer> set = new HashSet<>();
public static void main(String[] args) throws Exception {
Read in = new Read();
set.clear();
n = in.nextInt();
for (int i = 0; i < n; i++) {
nums[i] = in.nextInt();
Arrays.fill(memo[i],false);
}
Arrays.sort(nums,0,n);
dfs(n-1,0);
System.out.println(set.size()-1);
}
public static void dfs(int i,int sum) {
if (i < 0){
set.add(sum);
return;
}
// 重复的sum没有意义
if (memo[i][sum]){
return;
}
memo[i][sum]=true;
set.add(sum);
// 可以减去
if (sum > nums[i]){
dfs(i-1,sum-nums[i]);
}
// 不选则增加或减去
dfs(i-1,sum);
// 增加
dfs(i-1,sum+nums[i]);
}
}
class Read {
private StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public int nextInt() throws Exception {
st.nextToken();
return (int) st.nval;
}
public long nextLong() throws Exception {
st.nextToken();
return (long) st.nval;
}
}