class Solution {

public:

vector<int> productExceptSelf(vector<int>& nums) {

vector<int> output(nums.size(),1);

for(int i = nums.size()-2; i>=0 ;i--)

{

output[i] = output[i+1] * nums[i+1];

}

int temp = 1;

for(int i = 0; i<nums.size();i++)

{

output[i] = output[i] * temp;

temp = nums[i]* temp;

}

return output;

}

};

The most important point in this problem I think is the recurrence relation between the adjacent elements.

For example, in test case [1,2,3,4], for elements '2' and '3', their products of right side of the array are '3*4', which can be denoted as n_2, and '4', which can be denoted as n_3, respectively. We noted that the product n_2 is a recurrence from n_3, by n_3 times the number '3'. So are the same with the products of left side.