DataStructures-Algorithms/Leetcode Top Interview Questions/solutions/Pascals Triangle.cpp at master · arjunkumar09/DataStructures-Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
Pascal's Triangle
=================

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
*/

class Solution
{
public:
  vector<vector<int>> generate(int n)
  {
    if (n == 0)
      return {};
    if (n == 1)
      return {{1}};

    vector<vector<int>> ans;
    ans.push_back({1});
    ans.push_back({1, 1});

    for (int i = 3; i <= n; ++i)
    {
      vector<int> subans;
      subans.push_back(1);
      for (int j = 1; j <= i - 2; ++j)
        subans.push_back(ans[i - 2][j - 1] + ans[i - 2][j]);
      subans.push_back(1);
      ans.push_back(subans);
    }

    return ans;
  }
};