Question

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.

Solution

class Solution {
 public:
  vector<vector<int>> generate(int numRows) {
    vector<vector<int>> res;
    res.reserve(numRows);
    if (numRows < 0) return res;
    for (int n = 0; n < numRows; ++n) {
      vector<int> row;
      row.reserve(n);
      for (int i = 0; i <= n; ++i) row.emplace_back(combine(n, i));
      res.emplace_back(row);
    }
    return res;
  }

  long combine(int n, int c) {
    int i;
    long p = 1;
    for (i = 1; i <= c; i++) {
      p = p * (n - i + 1) / i;
    }
    return p;
  }
};