Posted on by Kalkicode
Code Backtracking

Print all n-digit strictly increasing numbers

The problem at hand is to generate and print all n-digit strictly increasing numbers. A strictly increasing number is a number in which each digit is greater than the digit to its left. This program aims to create a mechanism for generating and displaying all such n-digit strictly increasing numbers.

Problem Statement

Given a positive integer n, the goal is to generate and print all n-digit strictly increasing numbers.

Example

Let's illustrate the problem with an example. For n = 2, the program should generate and print all possible 2-digit strictly increasing numbers. The expected output is a list of these numbers:

01 02 03 04 05 06 07 08 09 12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89

Idea to Solve

To generate all n-digit strictly increasing numbers, a recursive approach is often useful. The idea is to start with an empty string, iterate through digits from 0 to 9, and append each digit to the string while making sure it's greater than the previous digit. This process continues recursively until the desired number of digits is reached.

Pseudocode

function increasingNumbers(result, currentDigit, remainingDigits):
    if remainingDigits is 0:
        print result
    else:
        for nextDigit from currentDigit + 1 to 9:
            increasingNumbers(result + nextDigit, nextDigit, remainingDigits - 1)

function generateIncreasingNumbers(n):
    increasingNumbers("", -1, n)

Algorithm Explanation

  1. The increasingNumbers function takes three parameters: result (the currently generated number), currentDigit (the last digit added), and remainingDigits (the number of digits left to add).
  2. If remainingDigits is 0, it means a number with the desired number of digits has been generated, so the result is printed.
  3. Otherwise, a loop runs from currentDigit + 1 to 9 (since we need strictly increasing digits).
  4. For each digit in the loop, the increasingNumbers function is called recursively with an updated result, the new digit as currentDigit, and remainingDigits - 1.
  5. This recursive process continues until all possible combinations are generated and printed.

Code Solution

/*
    Java Program for
    Print all n-digit strictly increasing numbers 
*/
public class Numbers
{
    public void increasingNo(String result, int i, int digit)
    {
        if (digit == 0)
        {
            // Display result
            System.out.print(" "+result);
        }
        else
        {
          	// Execute loop from i to 9
            for (int j = i; j <= 9; j++)
            {
              	// Find increasing number using recursion
                increasingNo(result + j, j + 1, digit - 1);
            }
        }
    }
    public static void main(String[] args)
    {
        Numbers task = new Numbers();
		// When digit is 4
        task.increasingNo("", 0, 4);
      	System.out.print("\n");
      	// When digit is 2
      	task.increasingNo("", 0, 2);
    }
}

input

 0123 0124 0125 0126 0127 0128 0129 0134 0135 0136 0137 0138 0139 0145 0146 0147 0148 0149 0156 0157 0158 0159 0167 0168 0169 0178 0179 0189 0234 0235 0236 0237 0238 0239 0245 0246 0247 0248 0249 0256 0257 0258 0259 0267 0268 0269 0278 0279 0289 0345 0346 0347 0348 0349 0356 0357 0358 0359 0367 0368 0369 0378 0379 0389 0456 0457 0458 0459 0467 0468 0469 0478 0479 0489 0567 0568 0569 0578 0579 0589 0678 0679 0689 0789 1234 1235 1236 1237 1238 1239 1245 1246 1247 1248 1249 1256 1257 1258 1259 1267 1268 1269 1278 1279 1289 1345 1346 1347 1348 1349 1356 1357 1358 1359 1367 1368 1369 1378 1379 1389 1456 1457 1458 1459 1467 1468 1469 1478 1479 1489 1567 1568 1569 1578 1579 1589 1678 1679 1689 1789 2345 2346 2347 2348 2349 2356 2357 2358 2359 2367 2368 2369 2378 2379 2389 2456 2457 2458 2459 2467 2468 2469 2478 2479 2489 2567 2568 2569 2578 2579 2589 2678 2679 2689 2789 3456 3457 3458 3459 3467 3468 3469 3478 3479 3489 3567 3568 3569 3578 3579 3589 3678 3679 3689 3789 4567 4568 4569 4578 4579 4589 4678 4679 4689 4789 5678 5679 5689 5789 6789
 01 02 03 04 05 06 07 08 09 12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89
// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program for
    Print all n-digit strictly increasing numbers 
*/
class Numbers
{
	public: void increasingNo(string result, int i, int digit)
	{
		if (digit == 0)
		{
			// Display result
			cout << " " << result;
		}
		else
		{
			// Execute loop from i to 9
			for (int j = i; j <= 9; j++)
			{
				// Find increasing number using recursion
				this->increasingNo(result  +  to_string(j), j + 1, digit - 1);
			}
		}
	}
};
int main()
{
	Numbers *task = new Numbers();
	// When digit is 4
	task->increasingNo("", 0, 4);
	cout << "\n";
	// When digit is 2
	task->increasingNo("", 0, 2);
	return 0;
}

input

 0123 0124 0125 0126 0127 0128 0129 0134 0135 0136 0137 0138 0139 0145 0146 0147 0148 0149 0156 0157 0158 0159 0167 0168 0169 0178 0179 0189 0234 0235 0236 0237 0238 0239 0245 0246 0247 0248 0249 0256 0257 0258 0259 0267 0268 0269 0278 0279 0289 0345 0346 0347 0348 0349 0356 0357 0358 0359 0367 0368 0369 0378 0379 0389 0456 0457 0458 0459 0467 0468 0469 0478 0479 0489 0567 0568 0569 0578 0579 0589 0678 0679 0689 0789 1234 1235 1236 1237 1238 1239 1245 1246 1247 1248 1249 1256 1257 1258 1259 1267 1268 1269 1278 1279 1289 1345 1346 1347 1348 1349 1356 1357 1358 1359 1367 1368 1369 1378 1379 1389 1456 1457 1458 1459 1467 1468 1469 1478 1479 1489 1567 1568 1569 1578 1579 1589 1678 1679 1689 1789 2345 2346 2347 2348 2349 2356 2357 2358 2359 2367 2368 2369 2378 2379 2389 2456 2457 2458 2459 2467 2468 2469 2478 2479 2489 2567 2568 2569 2578 2579 2589 2678 2679 2689 2789 3456 3457 3458 3459 3467 3468 3469 3478 3479 3489 3567 3568 3569 3578 3579 3589 3678 3679 3689 3789 4567 4568 4569 4578 4579 4589 4678 4679 4689 4789 5678 5679 5689 5789 6789
 01 02 03 04 05 06 07 08 09 12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89
package main
import "strconv"
import "fmt"
/*
    Go Program for
    Print all n-digit strictly increasing numbers 
*/
func increasingNo(result string, i int, digit int) {
	if digit == 0 {
		// Display result
		fmt.Print(" ", result)
	} else {
		// Execute loop from i to 9
		for j := i ; j <= 9 ; j++ {
			// Find increasing number using recursion
			increasingNo(result + strconv.Itoa(j), j + 1, digit - 1)
		}
	}
}
func main() {

	// When digit is 4
	increasingNo("", 0, 4)
	fmt.Print("\n")
	// When digit is 2
	increasingNo("", 0, 2)
}

input

 0123 0124 0125 0126 0127 0128 0129 0134 0135 0136 0137 0138 0139 0145 0146 0147 0148 0149 0156 0157 0158 0159 0167 0168 0169 0178 0179 0189 0234 0235 0236 0237 0238 0239 0245 0246 0247 0248 0249 0256 0257 0258 0259 0267 0268 0269 0278 0279 0289 0345 0346 0347 0348 0349 0356 0357 0358 0359 0367 0368 0369 0378 0379 0389 0456 0457 0458 0459 0467 0468 0469 0478 0479 0489 0567 0568 0569 0578 0579 0589 0678 0679 0689 0789 1234 1235 1236 1237 1238 1239 1245 1246 1247 1248 1249 1256 1257 1258 1259 1267 1268 1269 1278 1279 1289 1345 1346 1347 1348 1349 1356 1357 1358 1359 1367 1368 1369 1378 1379 1389 1456 1457 1458 1459 1467 1468 1469 1478 1479 1489 1567 1568 1569 1578 1579 1589 1678 1679 1689 1789 2345 2346 2347 2348 2349 2356 2357 2358 2359 2367 2368 2369 2378 2379 2389 2456 2457 2458 2459 2467 2468 2469 2478 2479 2489 2567 2568 2569 2578 2579 2589 2678 2679 2689 2789 3456 3457 3458 3459 3467 3468 3469 3478 3479 3489 3567 3568 3569 3578 3579 3589 3678 3679 3689 3789 4567 4568 4569 4578 4579 4589 4678 4679 4689 4789 5678 5679 5689 5789 6789
 01 02 03 04 05 06 07 08 09 12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89
// Include namespace system
using System;
/*
    Csharp Program for
    Print all n-digit strictly increasing numbers 
*/
public class Numbers
{
	public void increasingNo(String result, int i, int digit)
	{
		if (digit == 0)
		{
			// Display result
			Console.Write(" " + result);
		}
		else
		{
			// Execute loop from i to 9
			for (int j = i; j <= 9; j++)
			{
				// Find increasing number using recursion
				this.increasingNo(result + j, j + 1, digit - 1);
			}
		}
	}
	public static void Main(String[] args)
	{
		Numbers task = new Numbers();
		// When digit is 4
		task.increasingNo("", 0, 4);
		Console.Write("\n");
		// When digit is 2
		task.increasingNo("", 0, 2);
	}
}

input

 0123 0124 0125 0126 0127 0128 0129 0134 0135 0136 0137 0138 0139 0145 0146 0147 0148 0149 0156 0157 0158 0159 0167 0168 0169 0178 0179 0189 0234 0235 0236 0237 0238 0239 0245 0246 0247 0248 0249 0256 0257 0258 0259 0267 0268 0269 0278 0279 0289 0345 0346 0347 0348 0349 0356 0357 0358 0359 0367 0368 0369 0378 0379 0389 0456 0457 0458 0459 0467 0468 0469 0478 0479 0489 0567 0568 0569 0578 0579 0589 0678 0679 0689 0789 1234 1235 1236 1237 1238 1239 1245 1246 1247 1248 1249 1256 1257 1258 1259 1267 1268 1269 1278 1279 1289 1345 1346 1347 1348 1349 1356 1357 1358 1359 1367 1368 1369 1378 1379 1389 1456 1457 1458 1459 1467 1468 1469 1478 1479 1489 1567 1568 1569 1578 1579 1589 1678 1679 1689 1789 2345 2346 2347 2348 2349 2356 2357 2358 2359 2367 2368 2369 2378 2379 2389 2456 2457 2458 2459 2467 2468 2469 2478 2479 2489 2567 2568 2569 2578 2579 2589 2678 2679 2689 2789 3456 3457 3458 3459 3467 3468 3469 3478 3479 3489 3567 3568 3569 3578 3579 3589 3678 3679 3689 3789 4567 4568 4569 4578 4579 4589 4678 4679 4689 4789 5678 5679 5689 5789 6789
 01 02 03 04 05 06 07 08 09 12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89
<?php
/*
    Php Program for
    Print all n-digit strictly increasing numbers 
*/
class Numbers
{
	public	function increasingNo($result, $i, $digit)
	{
		if ($digit == 0)
		{
			// Display result
			echo(" ".$result);
		}
		else
		{
			// Execute loop from i to 9
			for ($j = $i; $j <= 9; $j++)
			{
				// Find increasing number using recursion
				$this->increasingNo($result.strval($j), $j + 1, $digit - 1);
			}
		}
	}
}

function main()
{
	$task = new Numbers();
	// When digit is 4
	$task->increasingNo("", 0, 4);
	echo("\n");
	// When digit is 2
	$task->increasingNo("", 0, 2);
}
main();

input

 0123 0124 0125 0126 0127 0128 0129 0134 0135 0136 0137 0138 0139 0145 0146 0147 0148 0149 0156 0157 0158 0159 0167 0168 0169 0178 0179 0189 0234 0235 0236 0237 0238 0239 0245 0246 0247 0248 0249 0256 0257 0258 0259 0267 0268 0269 0278 0279 0289 0345 0346 0347 0348 0349 0356 0357 0358 0359 0367 0368 0369 0378 0379 0389 0456 0457 0458 0459 0467 0468 0469 0478 0479 0489 0567 0568 0569 0578 0579 0589 0678 0679 0689 0789 1234 1235 1236 1237 1238 1239 1245 1246 1247 1248 1249 1256 1257 1258 1259 1267 1268 1269 1278 1279 1289 1345 1346 1347 1348 1349 1356 1357 1358 1359 1367 1368 1369 1378 1379 1389 1456 1457 1458 1459 1467 1468 1469 1478 1479 1489 1567 1568 1569 1578 1579 1589 1678 1679 1689 1789 2345 2346 2347 2348 2349 2356 2357 2358 2359 2367 2368 2369 2378 2379 2389 2456 2457 2458 2459 2467 2468 2469 2478 2479 2489 2567 2568 2569 2578 2579 2589 2678 2679 2689 2789 3456 3457 3458 3459 3467 3468 3469 3478 3479 3489 3567 3568 3569 3578 3579 3589 3678 3679 3689 3789 4567 4568 4569 4578 4579 4589 4678 4679 4689 4789 5678 5679 5689 5789 6789
 01 02 03 04 05 06 07 08 09 12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89
/*
    Node JS Program for
    Print all n-digit strictly increasing numbers 
*/
class Numbers
{
	increasingNo(result, i, digit)
	{
		if (digit == 0)
		{
			// Display result
			process.stdout.write(" " + result);
		}
		else
		{
			// Execute loop from i to 9
			for (var j = i; j <= 9; j++)
			{
				// Find increasing number using recursion
				this.increasingNo(result + j, j + 1, digit - 1);
			}
		}
	}
}

function main()
{
	var task = new Numbers();
	// When digit is 4
	task.increasingNo("", 0, 4);
	process.stdout.write("\n");
	// When digit is 2
	task.increasingNo("", 0, 2);
}
main();

input

 0123 0124 0125 0126 0127 0128 0129 0134 0135 0136 0137 0138 0139 0145 0146 0147 0148 0149 0156 0157 0158 0159 0167 0168 0169 0178 0179 0189 0234 0235 0236 0237 0238 0239 0245 0246 0247 0248 0249 0256 0257 0258 0259 0267 0268 0269 0278 0279 0289 0345 0346 0347 0348 0349 0356 0357 0358 0359 0367 0368 0369 0378 0379 0389 0456 0457 0458 0459 0467 0468 0469 0478 0479 0489 0567 0568 0569 0578 0579 0589 0678 0679 0689 0789 1234 1235 1236 1237 1238 1239 1245 1246 1247 1248 1249 1256 1257 1258 1259 1267 1268 1269 1278 1279 1289 1345 1346 1347 1348 1349 1356 1357 1358 1359 1367 1368 1369 1378 1379 1389 1456 1457 1458 1459 1467 1468 1469 1478 1479 1489 1567 1568 1569 1578 1579 1589 1678 1679 1689 1789 2345 2346 2347 2348 2349 2356 2357 2358 2359 2367 2368 2369 2378 2379 2389 2456 2457 2458 2459 2467 2468 2469 2478 2479 2489 2567 2568 2569 2578 2579 2589 2678 2679 2689 2789 3456 3457 3458 3459 3467 3468 3469 3478 3479 3489 3567 3568 3569 3578 3579 3589 3678 3679 3689 3789 4567 4568 4569 4578 4579 4589 4678 4679 4689 4789 5678 5679 5689 5789 6789
 01 02 03 04 05 06 07 08 09 12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89
#    Python 3 Program for
#    Print all n-digit strictly increasing numbers 
class Numbers :
	def increasingNo(self, result, i, digit) :
		if (digit == 0) :
			#  Display result
			print(" ", result, end = "")
		else :
			j = i
			#  Execute loop from i to 9
			while (j <= 9) :
				#  Find increasing number using recursion
				self.increasingNo(result + str(j), j + 1, digit - 1)
				j += 1

def main() :
	task = Numbers()
	#  When digit is 4
	task.increasingNo("", 0, 4)
	print(end = "\n")
	#  When digit is 2
	task.increasingNo("", 0, 2)

if __name__ == "__main__": main()

input

  0123  0124  0125  0126  0127  0128  0129  0134  0135  0136  0137  0138  0139  0145  0146  0147  0148  0149  0156  0157  0158  0159  0167  0168  0169  0178  0179  0189  0234  0235  0236  0237  0238  0239  0245  0246  0247  0248  0249  0256  0257  0258  0259  0267  0268  0269  0278  0279  0289  0345  0346  0347  0348  0349  0356  0357  0358  0359  0367  0368  0369  0378  0379  0389  0456  0457  0458  0459  0467  0468  0469  0478  0479  0489  0567  0568  0569  0578  0579  0589  0678  0679  0689  0789  1234  1235  1236  1237  1238  1239  1245  1246  1247  1248  1249  1256  1257  1258  1259  1267  1268  1269  1278  1279  1289  1345  1346  1347  1348  1349  1356  1357  1358  1359  1367  1368  1369  1378  1379  1389  1456  1457  1458  1459  1467  1468  1469  1478  1479  1489  1567  1568  1569  1578  1579  1589  1678  1679  1689  1789  2345  2346  2347  2348  2349  2356  2357  2358  2359  2367  2368  2369  2378  2379  2389  2456  2457  2458  2459  2467  2468  2469  2478  2479  2489  2567  2568  2569  2578  2579  2589  2678  2679  2689  2789  3456  3457  3458  3459  3467  3468  3469  3478  3479  3489  3567  3568  3569  3578  3579  3589  3678  3679  3689  3789  4567  4568  4569  4578  4579  4589  4678  4679  4689  4789  5678  5679  5689  5789  6789
  01  02  03  04  05  06  07  08  09  12  13  14  15  16  17  18  19  23  24  25  26  27  28  29  34  35  36  37  38  39  45  46  47  48  49  56  57  58  59  67  68  69  78  79  89
#    Ruby Program for
#    Print all n-digit strictly increasing numbers 
class Numbers 
	def increasingNo(result, i, digit) 
		if (digit == 0) 
			#  Display result
			print(" ", result)
		else
 
			j = i
			#  Execute loop from i to 9
			while (j <= 9) 
				#  Find increasing number using recursion
				self.increasingNo(result + j.to_s, j + 1, digit - 1)
				j += 1
			end

		end

	end

end

def main() 
	task = Numbers.new()
	#  When digit is 4
	task.increasingNo("", 0, 4)
	print("\n")
	#  When digit is 2
	task.increasingNo("", 0, 2)
end

main()

input

 0123 0124 0125 0126 0127 0128 0129 0134 0135 0136 0137 0138 0139 0145 0146 0147 0148 0149 0156 0157 0158 0159 0167 0168 0169 0178 0179 0189 0234 0235 0236 0237 0238 0239 0245 0246 0247 0248 0249 0256 0257 0258 0259 0267 0268 0269 0278 0279 0289 0345 0346 0347 0348 0349 0356 0357 0358 0359 0367 0368 0369 0378 0379 0389 0456 0457 0458 0459 0467 0468 0469 0478 0479 0489 0567 0568 0569 0578 0579 0589 0678 0679 0689 0789 1234 1235 1236 1237 1238 1239 1245 1246 1247 1248 1249 1256 1257 1258 1259 1267 1268 1269 1278 1279 1289 1345 1346 1347 1348 1349 1356 1357 1358 1359 1367 1368 1369 1378 1379 1389 1456 1457 1458 1459 1467 1468 1469 1478 1479 1489 1567 1568 1569 1578 1579 1589 1678 1679 1689 1789 2345 2346 2347 2348 2349 2356 2357 2358 2359 2367 2368 2369 2378 2379 2389 2456 2457 2458 2459 2467 2468 2469 2478 2479 2489 2567 2568 2569 2578 2579 2589 2678 2679 2689 2789 3456 3457 3458 3459 3467 3468 3469 3478 3479 3489 3567 3568 3569 3578 3579 3589 3678 3679 3689 3789 4567 4568 4569 4578 4579 4589 4678 4679 4689 4789 5678 5679 5689 5789 6789
 01 02 03 04 05 06 07 08 09 12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89
/*
    Scala Program for
    Print all n-digit strictly increasing numbers 
*/
class Numbers()
{
	def increasingNo(result: String, i: Int, digit: Int): Unit = {
		if (digit == 0)
		{
			// Display result
			print(" " + result);
		}
		else
		{
			var j: Int = i;
			// Execute loop from i to 9
			while (j <= 9)
			{
				// Find increasing number using recursion
				increasingNo(result + j.toString(), j + 1, digit - 1);
				j += 1;
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Numbers = new Numbers();
		// When digit is 4
		task.increasingNo("", 0, 4);
		print("\n");
		// When digit is 2
		task.increasingNo("", 0, 2);
	}
}

input

 0123 0124 0125 0126 0127 0128 0129 0134 0135 0136 0137 0138 0139 0145 0146 0147 0148 0149 0156 0157 0158 0159 0167 0168 0169 0178 0179 0189 0234 0235 0236 0237 0238 0239 0245 0246 0247 0248 0249 0256 0257 0258 0259 0267 0268 0269 0278 0279 0289 0345 0346 0347 0348 0349 0356 0357 0358 0359 0367 0368 0369 0378 0379 0389 0456 0457 0458 0459 0467 0468 0469 0478 0479 0489 0567 0568 0569 0578 0579 0589 0678 0679 0689 0789 1234 1235 1236 1237 1238 1239 1245 1246 1247 1248 1249 1256 1257 1258 1259 1267 1268 1269 1278 1279 1289 1345 1346 1347 1348 1349 1356 1357 1358 1359 1367 1368 1369 1378 1379 1389 1456 1457 1458 1459 1467 1468 1469 1478 1479 1489 1567 1568 1569 1578 1579 1589 1678 1679 1689 1789 2345 2346 2347 2348 2349 2356 2357 2358 2359 2367 2368 2369 2378 2379 2389 2456 2457 2458 2459 2467 2468 2469 2478 2479 2489 2567 2568 2569 2578 2579 2589 2678 2679 2689 2789 3456 3457 3458 3459 3467 3468 3469 3478 3479 3489 3567 3568 3569 3578 3579 3589 3678 3679 3689 3789 4567 4568 4569 4578 4579 4589 4678 4679 4689 4789 5678 5679 5689 5789 6789
 01 02 03 04 05 06 07 08 09 12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89
/*
    Swift 4 Program for
    Print all n-digit strictly increasing numbers 
*/
class Numbers
{
	func increasingNo(_ result: String, _ i: Int, _ digit: Int)
	{
		if (digit == 0)
		{
			// Display result
			print(" ", result, terminator: "");
		}
		else
		{
			var j = i;
			// Execute loop from i to 9
			while (j <= 9)
			{
				// Find increasing number using recursion
				self.increasingNo(result + String(j), j + 1, digit - 1);
				j += 1;
			}
		}
	}
}
func main()
{
	let task = Numbers();
	// When digit is 4
	task.increasingNo("", 0, 4);
	print(terminator: "\n");
	// When digit is 2
	task.increasingNo("", 0, 2);
}
main();

input

  0123  0124  0125  0126  0127  0128  0129  0134  0135  0136  0137  0138  0139  0145  0146  0147  0148  0149  0156  0157  0158  0159  0167  0168  0169  0178  0179  0189  0234  0235  0236  0237  0238  0239  0245  0246  0247  0248  0249  0256  0257  0258  0259  0267  0268  0269  0278  0279  0289  0345  0346  0347  0348  0349  0356  0357  0358  0359  0367  0368  0369  0378  0379  0389  0456  0457  0458  0459  0467  0468  0469  0478  0479  0489  0567  0568  0569  0578  0579  0589  0678  0679  0689  0789  1234  1235  1236  1237  1238  1239  1245  1246  1247  1248  1249  1256  1257  1258  1259  1267  1268  1269  1278  1279  1289  1345  1346  1347  1348  1349  1356  1357  1358  1359  1367  1368  1369  1378  1379  1389  1456  1457  1458  1459  1467  1468  1469  1478  1479  1489  1567  1568  1569  1578  1579  1589  1678  1679  1689  1789  2345  2346  2347  2348  2349  2356  2357  2358  2359  2367  2368  2369  2378  2379  2389  2456  2457  2458  2459  2467  2468  2469  2478  2479  2489  2567  2568  2569  2578  2579  2589  2678  2679  2689  2789  3456  3457  3458  3459  3467  3468  3469  3478  3479  3489  3567  3568  3569  3578  3579  3589  3678  3679  3689  3789  4567  4568  4569  4578  4579  4589  4678  4679  4689  4789  5678  5679  5689  5789  6789
  01  02  03  04  05  06  07  08  09  12  13  14  15  16  17  18  19  23  24  25  26  27  28  29  34  35  36  37  38  39  45  46  47  48  49  56  57  58  59  67  68  69  78  79  89
/*
    Kotlin Program for
    Print all n-digit strictly increasing numbers 
*/
class Numbers
{
	fun increasingNo(result: String, i: Int, digit: Int): Unit
	{
		if (digit == 0)
		{
			// Display result
			print(" " + result);
		}
		else
		{
			var j: Int = i;
			// Execute loop from i to 9
			while (j <= 9)
			{
				// Find increasing number using recursion
				this.increasingNo(result + j.toString(), j + 1, digit - 1);
				j += 1;
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Numbers = Numbers();
	// When digit is 4
	task.increasingNo("", 0, 4);
	print("\n");
	// When digit is 2
	task.increasingNo("", 0, 2);
}

input

 0123 0124 0125 0126 0127 0128 0129 0134 0135 0136 0137 0138 0139 0145 0146 0147 0148 0149 0156 0157 0158 0159 0167 0168 0169 0178 0179 0189 0234 0235 0236 0237 0238 0239 0245 0246 0247 0248 0249 0256 0257 0258 0259 0267 0268 0269 0278 0279 0289 0345 0346 0347 0348 0349 0356 0357 0358 0359 0367 0368 0369 0378 0379 0389 0456 0457 0458 0459 0467 0468 0469 0478 0479 0489 0567 0568 0569 0578 0579 0589 0678 0679 0689 0789 1234 1235 1236 1237 1238 1239 1245 1246 1247 1248 1249 1256 1257 1258 1259 1267 1268 1269 1278 1279 1289 1345 1346 1347 1348 1349 1356 1357 1358 1359 1367 1368 1369 1378 1379 1389 1456 1457 1458 1459 1467 1468 1469 1478 1479 1489 1567 1568 1569 1578 1579 1589 1678 1679 1689 1789 2345 2346 2347 2348 2349 2356 2357 2358 2359 2367 2368 2369 2378 2379 2389 2456 2457 2458 2459 2467 2468 2469 2478 2479 2489 2567 2568 2569 2578 2579 2589 2678 2679 2689 2789 3456 3457 3458 3459 3467 3468 3469 3478 3479 3489 3567 3568 3569 3578 3579 3589 3678 3679 3689 3789 4567 4568 4569 4578 4579 4589 4678 4679 4689 4789 5678 5679 5689 5789 6789
 01 02 03 04 05 06 07 08 09 12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89

Time Complexity

The time complexity of this solution depends on the number of strictly increasing numbers we need to generate. In the worst case, the program generates and prints all possible combinations of strictly increasing digits, resulting in an exponential time complexity. However, due to the nature of strictly increasing numbers, the actual number of combinations is limited. Thus, the average-case time complexity is significantly lower than the worst-case scenario.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment