At first I told the backtracking approach for the problem, whose time complexity was exponential. Then the interviewer asked me if it was possible to reduce the time complexity. Then I memoized my approach as there were lot of recurring subproblems and explained how it will give a much lesser time complexity of O(n^2).