leetcode 119 timeout

Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3, Return  [1,3,3,1] .
Note:
Could you optimize your algorithm to use only O(k) extra space?
この問題は最初は思いもよらなかったが,記録しなければならないので,一度やっている時間がある.

public List getRow(int rowIndex) {
		List ret=new ArrayList();
		if(rowIndex<0){
			return ret;
		}
		for(int k=0;k<=rowIndex;k++){
			ret.add(0);
			
		}
		ret.set(0, 1);
		for(int j=1;j<=rowIndex;j++){
			for(int i=j;i>0;i--){
				ret.set(i, ret.get(i)+ret.get(i-1));
			}
		}
		
		return ret;

	}

再帰タイムアウト、私が始めたばかりの方法

public Integer found(int i,int j){
		if(j==0||j==i){
			return 1;
		}else{
			int ret=found(i-1,j-1)+found(i-1,j);
			return ret;
		}
	}