[Coding test] 2. Combination and Permutation

combi

https://velog.io/@whitehousechef/Leetcode-39.-Combination-Sum

permutation

https://neetcode.io/problems/permutations?list=neetcode150

Unlike combinations https://velog.io/@whitehousechef/Leetcode-39.-Combination-Sum

permutation im thinking of using visited list and if its not a visited index we mark it as visited and iter from the same index as the index that i passed as parameter to my backtracking function is that ok?

I got the first part right but passing the same index as the parameter of my dfs function is for combinations. This is cuz for combination, we start from the current index to avoid reusing earlier elements. But for permu, we must loop thru entire array cuz order matters.

sol (permu)

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        ans = []
        n = len(nums)
        visited = [False] * n
        
        def dfs(tmp):
            # Base Case: permutation is complete
            if len(tmp) == n:
                ans.append(list(tmp)) # Create a copy of the current list
                return
            
            for i in range(n):
                if not visited[i]:
                    # Action
                    visited[i] = True
                    tmp.append(nums[i])
                    
                    # Recurse
                    dfs(tmp)
                    
                    # Backtrack (Undo Action)
                    tmp.pop()
                    visited[i] = False
        
        dfs([])
        return ans

sol (combi)

class Solution:
    def combinationSum(self, nums: list[int], target: int) -> list[list[int]]:
        ans = []
        
        def dfs(index, current_sum, so_far):
            # Base Case: exceeded target
            if current_sum > target:
                return
            
            # Base Case: reached target
            if current_sum == target:
                ans.append(list(so_far)) # Create a copy of the current path
                return
            
            # Recursive step: try candidates starting from 'index'
            # (Using 'index' allows us to reuse the same number multiple times)
            for i in range(index, len(nums)):
                so_far.append(nums[i])
                # Note: we pass i as the next index to allow reuse of nums[i]
                dfs(i, current_sum + nums[i], so_far)
                # Backtrack
                so_far.pop()

        dfs(0, 0, [])
        return ans

complexity

permu:
theres n! total poss and we are adding tmp list to ans list, ans.add(new ArrayList<>(tmp)) — i.e., making a copy of the current path thats n

so time is n! *n

n space? yes recursion depth

combi:
when generating combi of size k from n elements it is nCk and we add that to ans list so total time is
n* nCk

space:
k space recursion depth