Dsa
Backtracking
Medium
Paint Fences
You are tasked with painting n fences. Each fence can be painted in one of k colors. You want to paint all fences such that no more than two adjacent fences are painted the same color. Write a program that determines how many valid ways you can paint all the fences.
Input:
The first line contains two integers n and k (1 <= n <= 15, 1 <= k <= 5).
Output:
Print a single integer representing the number of valid ways to paint the fences.
Example:
Input:
3 2
Output:
6
Key concepts
backtrackingcombinatoricsrecursion
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now