Sponsored
Sponsored
This approach involves generating Pascal's Triangle row by row using an iterative method. The first row is initialized with [1], and for each subsequent row, the first and last element are always 1. The intermediate elements are calculated as sums of appropriate elements from the previous row.
Time Complexity: O(numRows^2) due to the nested loop structure.
Space Complexity: O(numRows^2) as we store all elements of the triangle.
1#include <iostream>
2#include <vector>
3
4std::vector<std::vector<int>> generate(int numRows) {
5 std::vector<std::vector<int>> triangle(numRows);
6 for (int i = 0; i < numRows; i++) {
7 triangle[i].resize(i + 1);
8 triangle[i][0] = 1;
9 triangle[i][i] = 1;
10 for (int j = 1; j < i; j++) {
11 triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
12 }
13 }
14 return triangle;
15}
16
17int main() {
18 int numRows = 5;
19 std::vector<std::vector<int>> result = generate(numRows);
20 for (const auto& row : result) {
21 for (int num : row) {
22 std::cout << num << " ";
23 }
24 std::cout << std::endl;
25 }
26 return 0;
27}
28In this C++ implementation, we utilize the vector container to create a 2D vector representing the Pascal's Triangle. Each row is resized to the appropriate size and populated, with the ends set to 1 and the middle calculated as the sum of elements from the previous row.
This approach constructs Pascal's Triangle using recursion by calculating each value based on the combination formula. The values on the edges are always 1, and other values are calculated as combinatorial numbers derived recursively.
Time Complexity: O(numRows^3) due to recursive calls, not optimal.
Space Complexity: O(numRows^2) for storing the triangle.
1using System.Collections.Generic;
public class PascalTriangleRecursive {
public static int Combination(int n, int k) {
if (k == 0 || k == n) return 1;
return Combination(n - 1, k - 1) + Combination(n - 1, k);
}
public static List<List<int>> Generate(int numRows) {
List<List<int>> triangle = new List<List<int>>();
for (int i = 0; i < numRows; i++) {
List<int> row = new List<int>();
for (int j = 0; j <= i; j++) {
row.Add(Combination(i, j));
}
triangle.Add(row);
}
return triangle;
}
public static void Main(string[] args) {
int numRows = 5;
List<List<int>> result = Generate(numRows);
foreach (var row in result) {
Console.WriteLine(string.Join(" ", row));
}
}
}
This C# program uses a recursive function to obtain Pascal's Triangle values by calculating each position's combinatorial value. Recursive computation helps build each row of the triangle effectively from the top down.