Inverse Coin Change

// Accepted solution for LeetCode #3592: Inverse Coin Change
// Auto-generated Java example from go.
class Solution {
    public void exampleSolution() {
    }
}
// Reference (go):
// // Accepted solution for LeetCode #3592: Inverse Coin Change
// package main
// 
// // https://space.bilibili.com/206214
// func findCoins(numWays []int) (ans []int) {
// 	n := len(numWays)
// 	f := make([]int, n+1)
// 	f[0] = 1
// 	for i := 1; i <= n; i++ {
// 		ways := numWays[i-1]
// 		if ways == f[i] {
// 			continue
// 		}
// 		if ways-1 != f[i] {
// 			return nil
// 		}
// 		ans = append(ans, i)
// 		// 现在得到了一个大小为 i 的物品，用 i 计算完全背包
// 		for j := i; j <= n; j++ {
// 			f[j] += f[j-i]
// 		}
// 	}
// 	return
// }

// Accepted solution for LeetCode #3592: Inverse Coin Change
package main

// https://space.bilibili.com/206214
func findCoins(numWays []int) (ans []int) {
	n := len(numWays)
	f := make([]int, n+1)
	f[0] = 1
	for i := 1; i <= n; i++ {
		ways := numWays[i-1]
		if ways == f[i] {
			continue
		}
		if ways-1 != f[i] {
			return nil
		}
		ans = append(ans, i)
		// 现在得到了一个大小为 i 的物品，用 i 计算完全背包
		for j := i; j <= n; j++ {
			f[j] += f[j-i]
		}
	}
	return
}

# Accepted solution for LeetCode #3592: Inverse Coin Change
# Time:  O(n^2)
# Space: O(1)

# dp
class Solution(object):
    def findCoins(self, numWays):
        """
        :type numWays: List[int]
        :rtype: List[int]
        """
        result = []
        for i in xrange(1, len(numWays)+1):
            if numWays[i-1] == 1:
                result.append(i)
                for j in reversed(xrange(i, len(numWays)+1)):
                    numWays[j-1] -= numWays[(j-i)-1] if (j-i)-1 >= 0 else 1
            if numWays[i-1]:
                return []
        return result


# Time:  O(n^2)
# Space: O(n)
# dp
class Solution2(object):
    def findCoins(self, numWays):
        """
        :type numWays: List[int]
        :rtype: List[int]
        """
        result = []
        dp = [0]*(len(numWays)+1)
        dp[0] = 1
        for i in xrange(1, len(numWays)+1):
            if numWays[i-1]-dp[i] == 1:
                result.append(i)
                for j in xrange(i, len(numWays)+1):
                    dp[j] += dp[j-i]
            if numWays[i-1]-dp[i]:
                return []
        return result

// Accepted solution for LeetCode #3592: Inverse Coin Change
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
    pub fn rust_example() {
        // Port the logic from the reference block below.
    }
}

// Reference (go):
// // Accepted solution for LeetCode #3592: Inverse Coin Change
// package main
// 
// // https://space.bilibili.com/206214
// func findCoins(numWays []int) (ans []int) {
// 	n := len(numWays)
// 	f := make([]int, n+1)
// 	f[0] = 1
// 	for i := 1; i <= n; i++ {
// 		ways := numWays[i-1]
// 		if ways == f[i] {
// 			continue
// 		}
// 		if ways-1 != f[i] {
// 			return nil
// 		}
// 		ans = append(ans, i)
// 		// 现在得到了一个大小为 i 的物品，用 i 计算完全背包
// 		for j := i; j <= n; j++ {
// 			f[j] += f[j-i]
// 		}
// 	}
// 	return
// }

// Accepted solution for LeetCode #3592: Inverse Coin Change
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3592: Inverse Coin Change
// package main
// 
// // https://space.bilibili.com/206214
// func findCoins(numWays []int) (ans []int) {
// 	n := len(numWays)
// 	f := make([]int, n+1)
// 	f[0] = 1
// 	for i := 1; i <= n; i++ {
// 		ways := numWays[i-1]
// 		if ways == f[i] {
// 			continue
// 		}
// 		if ways-1 != f[i] {
// 			return nil
// 		}
// 		ans = append(ans, i)
// 		// 现在得到了一个大小为 i 的物品，用 i 计算完全背包
// 		for j := i; j <= n; j++ {
// 			f[j] += f[j-i]
// 		}
// 	}
// 	return
// }