正整数无序拆分指将正整数n拆分为若干正整数之和,不计顺序且允许重复使用拆分项。现有如下四个递归实现选项,其中能正确计算拆分方案数的是?
int split(int n) { if(n == 0) return 1; int cnt = 0; for(int i=1; i<=n; i++) cnt += split(n-i); return cnt; }
int split(int n, int min_num) { if(n == 0) return 1; int cnt = 0; for(int i=min_num; i<=n; i++) { cnt += split(n - i, i); } return cnt; } // 调用时初始执行split(n, 1)
int split(int n) { if(n == 1 || n == 0) return 1; return split(n-1) + split(n-2); }
int split(int n, int max_num) { if(n == 0) return 1; if(n <0 || max_num ==0) return 0; return split(n, max_num+1) + split(n - max_num, max_num); }