a144 - 整數分拆

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出一個正整數 n 的所有整數分拆方式，並按照字典順序由大到小輸出。整數分拆是指將一個正整數表示為一系列正整數的和，且要求和式中的數列為非遞增順序。

解題思路

本題採用深度優先搜尋 (DFS) 的方式來產生所有可能的整數分拆。dfs 函數接收三個參數：rm (remaining)，表示剩餘需要分拆的數值；ma (maximum)，表示目前可以使用的最大數值（確保非遞增）；it (index)，表示目前已分拆數列的索引。

在 dfs 函數中，如果 rm 為 0，表示已經成功找到一個分拆，則輸出該分拆。否則，從 min(ma, rm) 開始迴圈，嘗試使用不同的數值 j 作為下一個分拆數。每次迴圈，將 j 加入分拆數列 a，並遞迴呼叫 dfs 函數，更新剩餘數值 rm 為 rm - j，最大數值 ma 保持不變，索引 it 加 1。迴圈從大到小進行，確保輸出結果按照字典順序排列。

主函數中，讀取輸入的整數 n，然後從 n 到 1 迴圈，每次將 i 作為第一個分拆數，並呼叫 dfs 函數開始分拆。

複雜度分析

• 時間複雜度: O(2^n)。在最壞情況下，需要遍歷所有可能的子集，因此時間複雜度是指數級的。
• 空間複雜度: O(n)。空間複雜度主要來自於遞迴的深度，以及儲存分拆數列 a 的空間。

程式碼

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[105];
void dfs(int rm,int ma,int it){
	if(rm==0){
		for(int i=0;i<it;++i){
			cout << a[i] << " ";
		}
		cout << "\n";
		return;
	}
	for(int j=min(ma,rm);j>=1;--j){
		a[it]=j;
		dfs(rm-j,j,it+1);
	}
}
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	while(cin >> n){
		for(int i=n;i>=1;--i){
			a[0]=i;
			dfs(n-i,i,1);
		}
	}
}