给定一个正整数n，生成所有可能的唯一方法，将n表示为正整数之和。
null
例如：
Input: n = 2 Output: 2 1 1 Input: n = 3 Output: 3 2 1 1 1 1 Note: 2+1 and 1+2 are considered as duplicates. Input: n = 4 Output: 4 3 1 2 2 2 1 1 1 1 1 1
解决方案： 我们按排序顺序打印所有分区，分区内的数字也按排序顺序打印（如上述示例所示）。其思想是使用当前分区中的值来获取下一个分区。我们将每个分区存储在数组p[]中。我们将p[]初始化为n，其中n是输入数。在每次迭代中。我们首先打印p[]，然后更新p[]以存储下一个分区。所以主要的问题是从给定的分区中获取下一个分区。
从当前分区获取下一个分区的步骤： 我们得到了p[]中的当前分区及其大小。我们需要更新p[]来存储下一个分区。p[]中的值必须按非递增顺序排序。
- 在p[]中找到最右边的非一个值，并将非一个值之前遇到的1的计数存储在变量rem_val中（它表示要更新的右侧值的总和）。让非一个值的索引为k。
- 将p[k]的值减少1，将rem_val增加1。现在可能有两种情况：
- a） 如果 p[k]大于或等于rem_val。这是一个简单的例子（我们在新分区中有排序顺序）。把rem_val放在p[k+1]，p[0…k+1]是我们的新分区。
- b） 否则 （这是一个有趣的例子，将初始p[]取为{3,1,1,1}，p[k]从3减少到2，rem_val从3增加到4，将rem_val除以大小为p[k]的不同值，并在p[k]之后的不同位置复制这些值，因此下一个分区应该是{2,2,2}）。
- 将p[k]复制到下一个位置，当p[k]小于rem_val时，增加k并减少p[k]的计数。最后，将rem_val放在p[k+1]，p[0…k+1]是我们的新分区。这一步就像用p[k]来划分rem_val（4除以2）。
以下是上述算法的实现：
C++
// CPP program to generate all unique // partitions of an integer #include<iostream> using namespace std; // A utility function to print an array p[] of size 'n' void printArray( int p[], int n) { for ( int i = 0; i < n; i++) cout << p[i] << " " ; cout << endl; } void printAllUniqueParts( int n) { int p[n]; // An array to store a partition int k = 0; // Index of last element in a partition p[k] = n; // Initialize first partition as number itself // This loop first prints current partition then generates next // partition. The loop stops when the current partition has all 1s while ( true ) { // print current partition printArray(p, k+1); // Generate next partition // Find the rightmost non-one value in p[]. Also, update the // rem_val so that we know how much value can be accommodated int rem_val = 0; while (k >= 0 && p[k] == 1) { rem_val += p[k]; k--; } // if k < 0, all the values are 1 so there are no more partitions if (k < 0) return ; // Decrease the p[k] found above and adjust the rem_val p[k]--; rem_val++; // If rem_val is more, then the sorted order is violated. Divide // rem_val in different values of size p[k] and copy these values at // different positions after p[k] while (rem_val > p[k]) { p[k+1] = p[k]; rem_val = rem_val - p[k]; k++; } // Copy rem_val to next position and increment position p[k+1] = rem_val; k++; } } // Driver program to test above functions int main() { cout << "All Unique Partitions of 2 " ; printAllUniqueParts(2); cout << "All Unique Partitions of 3 " ; printAllUniqueParts(3); cout << "All Unique Partitions of 4 " ; printAllUniqueParts(4); return 0; } |
JAVA
// Java program to generate all unique // partitions of an integer import java.io.*; class GFG { // Function to print an array p[] of size n static void printArray( int p[], int n) { for ( int i = 0 ; i < n; i++) System.out.print(p[i]+ " " ); System.out.println(); } // Function to generate all unique partitions of an integer static void printAllUniqueParts( int n) { int [] p = new int [n]; // An array to store a partition int k = 0 ; // Index of last element in a partition p[k] = n; // Initialize first partition as number itself // This loop first prints current partition then generates next // partition. The loop stops when the current partition has all 1s while ( true ) { // print current partition printArray(p, k+ 1 ); // Generate next partition // Find the rightmost non-one value in p[]. Also, update the // rem_val so that we know how much value can be accommodated int rem_val = 0 ; while (k >= 0 && p[k] == 1 ) { rem_val += p[k]; k--; } // if k < 0, all the values are 1 so there are no more partitions if (k < 0 ) return ; // Decrease the p[k] found above and adjust the rem_val p[k]--; rem_val++; // If rem_val is more, then the sorted order is violated. Divide // rem_val in different values of size p[k] and copy these values at // different positions after p[k] while (rem_val > p[k]) { p[k+ 1 ] = p[k]; rem_val = rem_val - p[k]; k++; } // Copy rem_val to next position and increment position p[k+ 1 ] = rem_val; k++; } } // Driver program public static void main (String[] args) { System.out.println( "All Unique Partitions of 2" ); printAllUniqueParts( 2 ); System.out.println( "All Unique Partitions of 3" ); printAllUniqueParts( 3 ); System.out.println( "All Unique Partitions of 4" ); printAllUniqueParts( 4 ); } } // Contributed by Pramod Kumar |
Python3
# A utility function to print an # array p[] of size 'n' def printArray(p, n): for i in range ( 0 , n): print (p[i], end = " " ) print () def printAllUniqueParts(n): p = [ 0 ] * n # An array to store a partition k = 0 # Index of last element in a partition p[k] = n # Initialize first partition # as number itself # This loop first prints current partition, # then generates next partition.The loop # stops when the current partition has all 1s while True : # print current partition printArray(p, k + 1 ) # Generate next partition # Find the rightmost non-one value in p[]. # Also, update the rem_val so that we know # how much value can be accommodated rem_val = 0 while k > = 0 and p[k] = = 1 : rem_val + = p[k] k - = 1 # if k < 0, all the values are 1 so # there are no more partitions if k < 0 : print () return # Decrease the p[k] found above # and adjust the rem_val p[k] - = 1 rem_val + = 1 # If rem_val is more, then the sorted # order is violated. Divide rem_val in # different values of size p[k] and copy # these values at different positions after p[k] while rem_val > p[k]: p[k + 1 ] = p[k] rem_val = rem_val - p[k] k + = 1 # Copy rem_val to next position # and increment position p[k + 1 ] = rem_val k + = 1 # Driver Code print ( 'All Unique Partitions of 2' ) printAllUniqueParts( 2 ) print ( 'All Unique Partitions of 3' ) printAllUniqueParts( 3 ) print ( 'All Unique Partitions of 4' ) printAllUniqueParts( 4 ) # This code is contributed # by JoshuaWorthington |
C#
// C# program to generate all unique // partitions of an integer using System; class GFG { // Function to print an array p[] // of size n static void printArray( int []p, int n) { for ( int i = 0; i < n; i++) Console.Write(p[i]+ " " ); Console.WriteLine(); } // Function to generate all unique // partitions of an integer static void printAllUniqueParts( int n) { // An array to store a partition int [] p = new int [n]; // Index of last element in a // partition int k = 0; // Initialize first partition as // number itself p[k] = n; // This loop first prints current // partition, then generates next // partition. The loop stops when // the current partition has all 1s while ( true ) { // print current partition printArray(p, k+1); // Generate next partition // Find the rightmost non-one // value in p[]. Also, update // the rem_val so that we know // how much value can be // accommodated int rem_val = 0; while (k >= 0 && p[k] == 1) { rem_val += p[k]; k--; } // if k < 0, all the values are 1 so // there are no more partitions if (k < 0) return ; // Decrease the p[k] found above // and adjust the rem_val p[k]--; rem_val++; // If rem_val is more, then the sorted // order is violated. Divide rem_val in // different values of size p[k] and copy // these values at different positions // after p[k] while (rem_val > p[k]) { p[k+1] = p[k]; rem_val = rem_val - p[k]; k++; } // Copy rem_val to next position and // increment position p[k+1] = rem_val; k++; } } // Driver program public static void Main () { Console.WriteLine( "All Unique Partitions of 2" ); printAllUniqueParts(2); Console.WriteLine( "All Unique Partitions of 3" ); printAllUniqueParts(3); Console.WriteLine( "All Unique Partitions of 4" ); printAllUniqueParts(4); } } // This code is contributed by Sam007. |
PHP
<?php // PHP program to generate // all unique partitions // of an integer // A utility function to // print an array p[] of // size 'n' function printArray( $p , $n ) { for ( $i = 0; $i < $n ; $i ++) echo $p [ $i ] , " " ; echo "" ; } function printAllUniqueParts( $n ) { // An array to store // a partition $p [ $n ] = array (0); // Index of last element // in a partition $k = 0; // Initialize first // partition as number // itself $p [ $k ] = $n ; // This loop first prints // current partition, then // generates next partition. // The loop stops when the // current partition has all 1s while (true) { // print current partition printArray( $p , $k + 1); // Generate next partition // Find the rightmost non-one // value in p[]. Also, update // the rem_val so that we know // how much value can be accommodated $rem_val = 0; while ( $k >= 0 && $p [ $k ] == 1) { $rem_val += $p [ $k ]; $k --; } // if k < 0, all the values // are 1 so there are no // more partitions if ( $k < 0) return ; // Decrease the p[k] found // above and adjust the // rem_val $p [ $k ]--; $rem_val ++; // If rem_val is more, then // the sorted order is violated. // Divide rem_val in different // values of size p[k] and copy // these values at different // positions after p[k] while ( $rem_val > $p [ $k ]) { $p [ $k + 1] = $p [ $k ]; $rem_val = $rem_val - $p [ $k ]; $k ++; } // Copy rem_val to next // position and increment // position $p [ $k + 1] = $rem_val ; $k ++; } } // Driver Code echo "All Unique Partitions of 2 " ; printAllUniqueParts(2); echo "All Unique Partitions of 3 " ; printAllUniqueParts(3); echo "All Unique Partitions of 4 " ; printAllUniqueParts(4); // This code is contributed // by akt_mit ?> |
Javascript
<script> // Javascript program to generate all unique // partitions of an integer // Function to print an array p[] // of size n function printArray(p, n) { for (let i = 0; i < n; i++) document.write(p[i] + " " ); document.write( "</br>" ); } // Function to generate all unique // partitions of an integer function printAllUniqueParts(n) { // An array to store a partition let p = new Array(n); // Index of last element in a // partition let k = 0; // Initialize first partition as // number itself p[k] = n; // This loop first prints current // partition, then generates next // partition. The loop stops when // the current partition has all 1s while ( true ) { // print current partition printArray(p, k + 1); // Generate next partition // Find the rightmost non-one // value in p[]. Also, update // the rem_val so that we know // how much value can be // accommodated let rem_val = 0; while (k >= 0 && p[k] == 1) { rem_val += p[k]; k--; } // If k < 0, all the values are 1 so // there are no more partitions if (k < 0) return ; // Decrease the p[k] found above // and adjust the rem_val p[k]--; rem_val++; // If rem_val is more, then the sorted // order is violated. Divide rem_val in // different values of size p[k] and copy // these values at different positions // after p[k] while (rem_val > p[k]) { p[k + 1] = p[k]; rem_val = rem_val - p[k]; k++; } // Copy rem_val to next position and // increment position p[k + 1] = rem_val; k++; } } // Driver code document.write( "All Unique Partitions of 2" + "</br>" ); printAllUniqueParts(2); document.write( "All Unique Partitions of 3" + "</br>" ); printAllUniqueParts(3); document.write( "All Unique Partitions of 4" + "</br>" ); printAllUniqueParts(4); // This code is contributed by divyesh072019 </script> |
输出：
All Unique Partitions of 2 2 1 1 All Unique Partitions of 3 3 2 1 1 1 1 All Unique Partitions of 4 4 3 1 2 2 2 1 1 1 1 1 1
时间复杂性： O（n*k）
辅助空间： O（n） 本文由 哈利帕朗 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
